We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Leaves of Binary Tree

Number: 366

Difficulty: Medium

Paid? Yes

Companies: LinkedIn, Google, Amazon

Problem Description

Given the root of a binary tree, repeatedly remove the leaves of the tree until the tree becomes empty. At each step, collect and return the values of the leaves that were removed.

Key Insights

  • Use a postorder traversal (bottom-up approach) to process the tree.
  • Determine the "height" of each node (distance from the deepest leaf) where leaves have a height of 1.
  • Group nodes by their computed height to simulate the layer-wise removal of leaves.
  • The same node may become a leaf after its children are removed.

Space and Time Complexity

Time Complexity: O(n) — Each node is visited exactly once. Space Complexity: O(n) — Space used for the recursion stack and the result list.

Solution

The solution uses a recursive helper function that performs a postorder traversal of the tree. For each node, it computes its height as max(height of left, height of right) + 1. Nodes with the same height are collected together in a list. This idea mirrors the process of removing leaves level by level, where leaves (height 1) are removed first, then their parents become new leaves, and so on. Data Structures used:

  • An array or list to maintain the groups of node values by their height. Algorithmic Approach:
  • Use Depth-First Search (DFS) via recursion.
  • Postorder traversal ensures that leaf nodes (base cases) are processed before their parents.
  • Append the node's value to the correct list based on the computed height.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val         # The value of the node.
        self.left = left       # Left child node.
        self.right = right     # Right child node.

class Solution:
    def findLeaves(self, root: TreeNode):
        result = []  # This will store lists of nodes at each removal step.

        def getHeight(node):
            # Base case: when the node is None, return 0.
            if not node:
                return 0
            # Recursively find the height of left and right subtrees.
            left_height = getHeight(node.left)
            right_height = getHeight(node.right)
            # Current node's height is max of left/right heights plus one.
            current_height = max(left_height, right_height) + 1
            # Ensure the result list has a sublist for the current height.
            if len(result) < current_height:
                result.append([])
            # Append the current node value to the corresponding height bucket.
            result[current_height - 1].append(node.val)
            return current_height

        getHeight(root)  # Start recursion from the root.
        return result
← Back to All Questions