Leaf-Similar Trees

Difficulty: Easy | Acceptance: 70.20% | Paid: No Topics: Tree, Depth-First Search, Binary Tree

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

• Examples
• Constraints
• Recursive DFS
• Iterative DFS
• Generator / Iterator

Examples

Example 1:

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

Example 2:

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

Constraints

The number of nodes in each tree will be in the range [1, 200].
Both of the given trees will have values in the range [0, 200].

Recursive DFS

Intuition We can perform a Depth-First Search (DFS) traversal on both trees. As we traverse, whenever we encounter a leaf node (a node with no left or right children), we record its value. After collecting the leaf values for both trees, we simply compare the two lists to see if they are identical.

Steps

• Define a helper function that takes a tree node and a list to store leaf values.
• If the node is null, return immediately.
• If the node is a leaf (both left and right children are null), add its value to the list.
• Recursively call the helper function for the left child, then the right child.
• Call the helper function for both root1 and root2 to generate their respective leaf sequences.
• Compare the two lists and return the result.

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def dfs(node, leaves):
            if not node:
                return
            if not node.left and not node.right:
                leaves.append(node.val)
                return
            dfs(node.left, leaves)
            dfs(node.right, leaves)
        
        leaves1 = []
        leaves2 = []
        dfs(root1, leaves1)
        dfs(root2, leaves2)
        return leaves1 == leaves2

Complexity

• Time: O(N + M), where N and M are the number of nodes in the two trees. We visit every node once.
• Space: O(N + M) to store the leaf sequences. In the worst case (skewed trees), the recursion stack depth can also be O(N) and O(M).

Iterative DFS

Intuition We can simulate the recursive DFS using an explicit stack. This avoids potential stack overflow issues (though unlikely given the constraints) and is a standard iterative approach for tree traversal. We maintain a stack for each tree and process nodes until we find the next leaf.

Steps

• Initialize two stacks, one for each tree root.
• Loop while both stacks are not empty.
• Inside the loop, process each stack to find the next leaf value.
  • Pop a node from the stack.
  • If it is a leaf, return its value.
  • Otherwise, push its right child, then its left child (to maintain left-to-right order).
• Compare the leaf values obtained from both trees. If they differ, return false.
• If the loop finishes, check if both stacks are empty (to handle cases where one tree has more leaves than the other).

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def dfs(stack):
            while stack:
                node = stack.pop()
                if not node.left and not node.right:
                    return node.val
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
            return None
        
        stack1 = [root1]
        stack2 = [root2]
        
        while stack1 and stack2:
            if dfs(stack1) != dfs(stack2):
                return False
        
        return not stack1 and not stack2

Complexity

• Time: O(N + M), as we traverse all nodes in both trees.
• Space: O(N + M) in the worst case for the stacks.

Generator / Iterator

Intuition Instead of storing all leaf values in lists, we can generate them on the fly using a generator (or an iterator). This allows us to compare leaves one by one. If we find a mismatch early, we can stop immediately without traversing the rest of the trees. This approach is memory efficient.

Steps

• Create a generator function that traverses the tree and yields leaf values one by one.
• Initialize two generators, one for each tree.
• Loop indefinitely, getting the next leaf value from both generators.
• If one generator finishes before the other, the trees are not leaf-similar.
• If the values differ at any point, return false.
• If both generators finish at the same time, return true.

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def dfs(node):
            if not node:
                return
            if not node.left and not node.right:
                yield node.val
            yield from dfs(node.left)
            yield from dfs(node.right)
        
        gen1 = dfs(root1)
        gen2 = dfs(root2)
        
        for v1, v2 in zip(gen1, gen2):
            if v1 != v2:
                return False
        
        # Check if both generators are exhausted
        # We consume the rest of one to see if it has more elements
        try:
            next(gen1)
            return False # gen1 has more elements
        except StopIteration:
            pass
        
        try:
            next(gen2)
            return False # gen2 has more elements
        except StopIteration:
            pass
            
        return True

Complexity

• Time: O(N + M), where N and M are the number of nodes in the two trees.
• Space: O(H1 + H2), where H1 and H2 are the heights of the trees. This is because we only store the recursion stack (or iterator stack) up to the current depth, rather than storing all leaves.