Teaching Kids Programming – Find Leaves of Binary Tree via Recursive Depth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the root of a binary tree, collect a tree’s nodes as if you were doing this:

1. Collect all the leaf nodes.
2. Remove all the leaf nodes.
3. Repeat until the tree is empty.

Example 1:

find-binary-tree-leaves

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

Example 2:
Input: root = [1]
Output: [[1]]

Constraints:
The number of nodes in the tree is in the range [1, 100].
-100 <= Node.val <= 100

Find Leaves of Binary Tree via Recursive Depth First Search Algorithm

The nodes at the same depth are to remove together. The max depth is defined as the max(L, R)+1 where L and R the max depth for left and right sub tree respectively. The leaf nodes have depth of one. And we can compute the max depth using Recursive DFS (Depth First Search) Algorithm. The depth values are propagated bottom up from the leaves to the root.

And we store the key value pairs in a dictionary where keys are depths, and the values are list of nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
        data = defaultdict(list)
        
        def dfs(root):
            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            d = max(left, right) + 1
            data[d].append(root.val)
            return d
        
        dfs(root)
        return data.values()

class Solution:
    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
        data = defaultdict(list)
        
        def dfs(root):
            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            d = max(left, right) + 1
            data[d].append(root.val)
            return d
        
        dfs(root)
        return data.values()

The time/space complexity is O(N) where N is the number of nodes in the given binary tree.

See also: Depth First Search Algorithm to Find Leaves of a Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —