872. Leaf-Similar Trees - Explanation

Problem Link

1. Depth First Search

Intuition

Two trees are leaf-similar if their leaf nodes, read from left to right, form the same sequence. We can collect the leaf values from each tree using a depth-first traversal. A node is a leaf if it has no children. By traversing left before right, we naturally encounter leaves in left-to-right order.

Algorithm

1. Create a helper function dfs that traverses a tree and appends leaf values to a list.
2. For each node:
   • If it's null, return immediately.
   • If it's a leaf (no left or right child), add its value to the list.
   • Otherwise, recursively process the left subtree, then the right subtree.
3. Collect leaves from both trees into separate lists.
4. Compare the two lists and return whether they are equal.

# 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
class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def dfs(root, leaf):
            if not root:
                return
            if not root.left and not root.right:
                leaf.append(root.val)
                return
            dfs(root.left, leaf)
            dfs(root.right, leaf)

        leaf1, leaf2 = [], []
        dfs(root1, leaf1)
        dfs(root2, leaf2)
        return leaf1 == leaf2

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(n + m)$

Where $n$ and $m$ are the number of nodes in the given trees.

---

2. Depth First Search (Space Optimized)

Intuition

Instead of storing both leaf sequences and comparing at the end, we can collect leaves from the first tree and then verify them against the second tree on the fly. By traversing the second tree in reverse order (right to left) and using a stack, we can pop leaves one by one and compare them immediately. This saves space when one tree has significantly fewer leaves than expected.

Algorithm

1. Traverse the first tree using DFS and store all leaf values in a stack (leaves appear in reverse order due to left-to-right traversal).
2. Define a second DFS function for the second tree that traverses right-to-left:
   • If a leaf is found, pop from the stack and compare. Return false on mismatch or if the stack is empty.
3. After traversing the second tree, check that the stack is empty (no extra leaves in the first tree).
4. Return true only if all leaves matched and both trees had the same number of leaves.

# 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
class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def dfs(root, leaf):
            if not root:
                return
            if not root.left and not root.right:
                leaf.append(root.val)
                return
            dfs(root.left, leaf)
            dfs(root.right, leaf)

        leaf1 = []
        dfs(root1, leaf1)

        def dfs1(root, leaf):
            if not root:
                return True
            if not root.left and not root.right:
                if not leaf:
                    return False
                return leaf.pop() == root.val
            return dfs1(root.right, leaf) and dfs1(root.left, leaf)

        return dfs1(root2, leaf1) and not leaf1

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(n + m)$

Where $n$ and $m$ are the number of nodes in the given trees.

---

3. Iterative DFS

Intuition

Rather than collecting all leaves first, we can compare leaves one at a time using two parallel iterative traversals. Each tree maintains its own stack. We advance each stack until we find the next leaf, compare the two leaves, and continue. This approach can exit early if a mismatch is found without traversing the entire trees.

Algorithm

1. Initialize two stacks, one for each tree, and push their root nodes.
2. Create a helper function getPathLeaf that pops nodes from a stack until a leaf is found, pushing children along the way.
3. While both stacks are non-empty:
   • Get the next leaf from each stack.
   • If the values differ, return false.
4. After the loop, return true only if both stacks are empty (both trees exhausted their leaves together).

# 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
class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def getPathLeaf(stack):
            while stack:
                node = stack.pop()
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
                if not node.left and not node.right:
                    return node.val

        stack1, stack2 = [root1], [root2]
        while stack1 and stack2:
            if getPathLeaf(stack1) != getPathLeaf(stack2):
                return False

        return not stack1 and not stack2

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(n + m)$

Where $n$ and $m$ are the number of nodes in the given trees.

---

Common Pitfalls

Collecting All Nodes Instead of Just Leaves

A common mistake is to collect all node values during traversal instead of only the leaf nodes. Remember that a leaf is specifically a node with no left and no right child. Including internal nodes in your comparison will produce incorrect results.

Traversing in Wrong Order (Right Before Left)

The problem requires leaves to match in left-to-right order. If you traverse right subtrees before left subtrees, you will collect leaves in the wrong sequence. Always process the left child before the right child in your DFS traversal.