Compare Leaf Traversal

Tags

Compare Leaf Traversal

Category

Binary Trees

Difficulty

Very Hard

Problem Statement

Given two binary trees, determine whether their leaf traversals are identical. The leaf traversal of a binary tree is the left-to-right sequence of its leaf nodes (nodes with no children). Two trees have the same leaf traversal if and only if reading the leaves from left to right produces the same sequence of values in both trees.

Intuition

The straightforward approach collects all leaves from each tree into a list and then compares the lists. This uses O(n1 + n2) space. A more elegant approach uses iterators (or coroutines/generators) to traverse both trees simultaneously, yielding one leaf at a time and comparing them on the fly. This way, we can short-circuit as soon as a mismatch is found and use only O(h1 + h2) space (the heights of the two trees for the stacks).

Approach

Approach 1: Collect and compare

  1. Perform an in-order (or pre-order) DFS on each tree, collecting leaf nodes into a list.
  2. Compare the two lists element by element.

Approach 2: Iterative with stacks (optimal)

  1. Maintain an explicit stack for each tree to simulate DFS.
  2. Write a helper function getNextLeaf(stack) that pops nodes from the stack, pushes right then left children, and returns when a leaf node is found.
  3. Repeatedly call getNextLeaf on both stacks. Compare the leaf values. If they differ, return false.
  4. After the loop, check that both stacks are exhausted (both trees have the same number of leaves). If one tree has remaining leaves and the other does not, return false.
  5. If all leaves matched, return true.

Pseudocode

function compareLeafTraversal(tree1, tree2):
    stack1 = [tree1]
    stack2 = [tree2]

    while stack1 is not empty and stack2 is not empty:
        leaf1 = getNextLeaf(stack1)
        leaf2 = getNextLeaf(stack2)

        if leaf1.value != leaf2.value:
            return false

    # Both should be exhausted
    return stack1 is empty and stack2 is empty

function getNextLeaf(stack):
    while true:
        node = stack.pop()
        if node.right is not null:
            stack.push(node.right)
        if node.left is not null:
            stack.push(node.left)
        if node.left is null and node.right is null:
            return node  # this is a leaf

Using generators (Python-style):

function compareLeafTraversal(tree1, tree2):
    gen1 = leafGenerator(tree1)
    gen2 = leafGenerator(tree2)

    for leaf1, leaf2 in zip_longest(gen1, gen2, fillvalue=SENTINEL):
        if leaf1 != leaf2:
            return false
    return true

generator leafGenerator(node):
    if node is null:
        return
    if node.left is null and node.right is null:
        yield node.value
        return
    yield from leafGenerator(node.left)
    yield from leafGenerator(node.right)

Time & Space Complexity

  • Time: O(n1 + n2) where n1 and n2 are the number of nodes in the two trees. In the best case (first leaves differ), the iterator approach terminates early in O(h1 + h2).
  • Space: O(h1 + h2) for the two stacks in the iterator approach, where h1 and h2 are the tree heights. The collect-and-compare approach uses O(L1 + L2) where L1 and L2 are the number of leaves.

Key Insights

  • Leaf traversal order is determined by the left-to-right DFS ordering, independent of the tree structure.
  • Using iterators/stacks to traverse both trees in lockstep avoids materializing the full leaf sequences and allows early termination.
  • Pushing right child before left child onto the stack ensures left-to-right traversal order.
  • The generator-based approach (in languages that support it) produces the cleanest and most readable code.
  • Two structurally different trees can have identical leaf traversals.

Edge Cases

  • Both trees are empty (null roots): return true (both have an empty leaf sequence).
  • One tree is empty and the other is not: return false (unless the non-empty tree somehow has no leaves, which is impossible for a valid tree with at least one node).
  • Both trees are single leaf nodes: compare their values directly.
  • Trees with the same structure but different leaf values: return false.
  • Trees with different structures but the same leaf values in the same order: return true.
  • A tree where every node is a leaf (single node): the leaf sequence is just that one node.
  • Very deep, skewed trees: the stack size equals the height, so this uses linear space in the worst case.

Linked mentions