How to Find Leaves of a Binary Tree [Java + Python]

Find Leaves of a Binary Tree: Problem + Solution in Java and Python

## Introduction to the Find Leaves of Binary Tree Problem

The Find Leaves of Binary Tree problem involves sequentially identifying all of the leaf nodes in a binary tree and returning their values. As with many tree problems, the solution requires the application of a traversal algorithm that visits nodes in the order most appropriate for this task, allowing for a linear time complexity.

## Example of the Find Leaves of a Binary Tree Interview Question

Given a binary tree, extract all the leaves in repeated succession into a list of lists by starting at the bottom and working your way upwards.

Input: Given the following TreeNode structure:

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

And given the following tree:

Plain text

[
    [44, 6, 2, 7],
    [14],
    [9],
    [5]
]

## 2 Ways to Find Leaves of a Binary Tree

The first things that ought to come to mind when thinking about trees are the approaches in which we can use to traverse them. There are pre-, in-, and post-order traversals, and also depth-first and breadth-first approaches. Perhaps asking the interviewer a little more might help us consider which of these will get us closer to the answer, and which will not.

Approach 1: Level-by-level

At this point, we can stare at the tree and think about various ways to do a traversal and what that might result in. The first thing that might come to mind, is that it looks a lot like a level-by-level extraction:

But that isn't exactly right. That'd give us this output:

Plain text

[
    [5],
    [9, 7],
    [44, 14],
    [6,2],
]

But it still isn't there yet. Let's look closer at the first sub-list -- what we want is to group the elements more like this:

This becomes the first sub-list in our result, and it's extracted by grabbing all elements, left-to-right, that don't have any children. We'll have this result so far:

Plain text

[
    [44, 6, 2, 7]
]

Approach 2: Depth-First Search (DFS)

So now that we’ve identified the need to focus on child nodes first we need to select an approach that will accomplish this, and the approach best-suited for this task is called depth-first search (DFS).

Extract Leaves Python Solution - Depth-first Search

PythonJava

#!/usr/env python3
from dataclasses import dataclass
from typing import List

@dataclass
class Node:
  val: int = 0
  left: 'Node' = None
  right: 'Node' = None

# our solution
def extractLeaves(root: Node):
  nonlocal answer = []

def dfs(n: Node):
    if not n:
      return -1

h = max(dfs(n.left), dfs(n.right)) + 1

if len(answer) <= h:
      answer.append([])

answer[h].append(n.val)

return h

dfs(root)
  return answer

def test(input: Node, desired: List[List[int]]):
  out = extractLeaves(input)
  if out == desired:
    print(f"PASS: {input} -> {desired}")
  else:
    print(f"FAIL! {input} -> {out}, expected {desired}")

def runTests():
  testTree = Node(5, Node(9, Node(44), Node(14, Node(6), Node(2))), Node(7))

test(None, [])
  test(Node(5), [[5]])
  test(testTree, [[44, 6, 2, 7], [14], [9], [5]])

runTests()

Time/Space Complexity