LeetCode 872 - Leaf-Similar Trees

LeetCode Problem 872

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to compare two binary trees based only on their leaf nodes. A leaf node is a node that has no left child and no right child. For each tree, we must collect the leaf values in left to right order, then determine whether the two resulting sequences are identical.

The important detail is that the overall structure of the trees does not matter. Two trees can look completely different internally and still be considered leaf-similar if their leaves appear in the same left to right order and contain the same values.

For example, suppose the first tree produces the leaf sequence:

[6, 7, 4, 9, 8]

and the second tree also produces:

[6, 7, 4, 9, 8]

Then the answer is true, even if the trees themselves are shaped differently.

The input consists of two root nodes, root1 and root2, each representing a binary tree. The expected output is a boolean value:

• true if both trees have the exact same leaf sequence
• false otherwise

The constraints tell us that each tree contains at most 200 nodes. This is a relatively small input size, so we do not need extremely advanced optimizations. A straightforward depth-first traversal is more than efficient enough.

Several edge cases are important to consider:

• Trees with only one node, where the root itself is the leaf
• Trees with different structures but identical leaf sequences
• Trees with the same leaf values but in different orders
• Trees with different numbers of leaves
• Deeply unbalanced trees, where recursion depth follows a long chain

The problem guarantees that each tree has at least one node, so we never receive an empty tree.

Approaches

Brute Force Approach

A brute-force style solution would repeatedly search each tree for the next leaf node and compare leaves one at a time. For every comparison, we might traverse large portions of the tree again to locate the next leaf.

This approach is correct because it eventually checks every leaf in left to right order. However, it is inefficient because the same nodes may be revisited many times during repeated searches.

In the worst case, this repeated traversal can lead to quadratic behavior.

Optimal Approach

The key insight is that we only care about the leaf sequence, not the internal tree structure.

We can perform a single depth-first traversal on each tree and record all leaf values in order. Since DFS naturally processes the left subtree before the right subtree, the collected leaves automatically appear in left to right order.

After collecting both sequences, we simply compare the two arrays.

This works efficiently because:

• Every node is visited exactly once
• Leaf detection is constant time
• Array comparison is linear

A recursive DFS is especially clean here because binary trees naturally fit recursive traversal patterns.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Repeatedly searches for leaves, revisiting nodes multiple times
Optimal	O(n + m)	O(n + m)	Single DFS traversal per tree, stores leaf sequences

Here:

• n is the number of nodes in the first tree
• m is the number of nodes in the second tree
• h is the tree height

Algorithm Walkthrough

1. Create an empty list to store leaf values for the first tree.

This list will preserve the left to right ordering of leaves encountered during traversal. 2. Perform a depth-first traversal on the first tree.

During traversal:

• If the current node is None, return immediately.
• If the node has no left child and no right child, it is a leaf node.
• Append the node's value to the leaf list.
• Otherwise, recursively process the left subtree first, then the right subtree.

3. Repeat the same process for the second tree.

This produces another leaf sequence list. 4. Compare the two leaf sequences.

If both lists are identical in both length and element order, return true. Otherwise, return false.

Why it works

The algorithm works because DFS visits nodes in left to right order when we recursively process the left child before the right child. Every leaf node is collected exactly once and appended in the correct order.

Since the definition of leaf-similar trees depends entirely on the ordered sequence of leaf values, comparing the two resulting lists directly gives the correct answer.

Python Solution

# 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

from typing import Optional, List

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

The implementation begins by defining a helper function called collect_leaves. This function performs a recursive DFS traversal.

The first condition checks whether the current node is None. If so, traversal stops immediately because there is no subtree to process.

Next, the function checks whether the current node is a leaf node. A node is considered a leaf when both left and right are None. In that case, its value is appended to the leaf sequence list.

If the node is not a leaf, recursion continues into the left subtree first and then the right subtree. This ordering is important because the problem requires leaves to be collected from left to right.

After defining the helper function, the solution creates two lists:

leaves1 = []
leaves2 = []

The DFS traversal fills these lists with the leaf sequences from each tree.

Finally, the solution compares the two lists directly using Python's list equality operator. This checks both:

• The number of leaves
• The exact ordering of leaf values

If both match, the method returns True.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
    leaves1 := []int{}
    leaves2 := []int{}

    var collectLeaves func(node *TreeNode, leaves *[]int)

    collectLeaves = func(node *TreeNode, leaves *[]int) {
        if node == nil {
            return
        }

        if node.Left == nil && node.Right == nil {
            *leaves = append(*leaves, node.Val)
            return
        }

        collectLeaves(node.Left, leaves)
        collectLeaves(node.Right, leaves)
    }

    collectLeaves(root1, &leaves1)
    collectLeaves(root2, &leaves2)

    if len(leaves1) != len(leaves2) {
        return false
    }

    for i := 0; i < len(leaves1); i++ {
        if leaves1[i] != leaves2[i] {
            return false
        }
    }

    return true
}

The Go implementation follows the same DFS strategy as the Python version.

One important difference is that slices are passed by reference using pointers:

func(node *TreeNode, leaves *[]int)

This allows the helper function to append directly into the shared slice.

Go does not support direct slice equality for non-nil slices, so we manually compare lengths and individual elements instead of writing:

leaves1 == leaves2

Nil handling is straightforward because Go uses nil pointers for missing children.

Integer overflow is not a concern because node values are limited to the range [0, 200].

Worked 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]

Traversing root1

Current Node	Leaf?	Leaf Sequence
3	No	[]
5	No	[]
6	Yes	[6]
2	No	[6]
7	Yes	[6, 7]
4	Yes	[6, 7, 4]
1	No	[6, 7, 4]
9	Yes	[6, 7, 4, 9]
8	Yes	[6, 7, 4, 9, 8]

Final sequence:

[6, 7, 4, 9, 8]

Traversing root2

Current Node	Leaf?	Leaf Sequence
3	No	[]
5	No	[]
6	Yes	[6]
7	Yes	[6, 7]
1	No	[6, 7]
4	Yes	[6, 7, 4]
2	No	[6, 7, 4]
9	Yes	[6, 7, 4, 9]
8	Yes	[6, 7, 4, 9, 8]

Final sequence:

[6, 7, 4, 9, 8]

Comparison:

[6, 7, 4, 9, 8] == [6, 7, 4, 9, 8]

Result:

true

Example 2

Input:

root1 = [1,2,3]
root2 = [1,3,2]

Traversing root1

Leaves collected:

[2, 3]

Traversing root2

Leaves collected:

[3, 2]

Comparison:

[2, 3] != [3, 2]

Result:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each node in both trees is visited exactly once
Space	O(n + m)	Leaf arrays plus recursion stack usage

The DFS traversal processes every node exactly one time, so the runtime is linear in the size of the two trees combined.

The extra space comes primarily from storing leaf sequences. In the worst case, about half the nodes may be leaves. The recursion stack also contributes up to O(h) space, where h is the height of the tree.

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = TreeNode(3)
root1.left = TreeNode(5)
root1.right = TreeNode(1)
root1.left.left = TreeNode(6)
root1.left.right = TreeNode(2)
root1.left.right.left = TreeNode(7)
root1.left.right.right = TreeNode(4)
root1.right.left = TreeNode(9)
root1.right.right = TreeNode(8)

root2 = TreeNode(3)
root2.left = TreeNode(5)
root2.right = TreeNode(1)
root2.left.left = TreeNode(6)
root2.left.right = TreeNode(7)
root2.right.left = TreeNode(4)
root2.right.right = TreeNode(2)
root2.right.right.left = TreeNode(9)
root2.right.right.right = TreeNode(8)

assert solution.leafSimilar(root1, root2) == True  # matching leaf sequences

# Example 2
root3 = TreeNode(1, TreeNode(2), TreeNode(3))
root4 = TreeNode(1, TreeNode(3), TreeNode(2))

assert solution.leafSimilar(root3, root4) == False  # same leaves, different order

# Single node trees
root5 = TreeNode(1)
root6 = TreeNode(1)

assert solution.leafSimilar(root5, root6) == True  # single identical leaf

# Different single node values
root7 = TreeNode(1)
root8 = TreeNode(2)

assert solution.leafSimilar(root7, root8) == False  # single different leaf

# Different number of leaves
root9 = TreeNode(1, TreeNode(2), TreeNode(3))
root10 = TreeNode(1, TreeNode(2))

assert solution.leafSimilar(root9, root10) == False  # different leaf counts

# Deep left-skewed tree
root11 = TreeNode(1)
root11.left = TreeNode(2)
root11.left.left = TreeNode(3)
root11.left.left.left = TreeNode(4)

root12 = TreeNode(4)

assert solution.leafSimilar(root11, root12) == True  # same single leaf value

# Trees with repeated leaf values
root13 = TreeNode(1)
root13.left = TreeNode(2)
root13.right = TreeNode(2)

root14 = TreeNode(3)
root14.left = TreeNode(2)
root14.right = TreeNode(2)

assert solution.leafSimilar(root13, root14) == True  # repeated leaves in same order

Test	Why
Matching example trees	Validates normal successful comparison
Same leaves, different order	Ensures order matters
Single identical nodes	Smallest valid input
Single different nodes	Detects unequal leaves immediately
Different number of leaves	Verifies sequence length comparison
Deep skewed tree	Tests recursive traversal on unbalanced trees
Repeated leaf values	Ensures duplicates are handled correctly

Edge Cases

Single Node Trees

A tree containing only one node is an important edge case because the root itself is also the leaf. Some implementations incorrectly assume leaves only appear deeper in the tree.

The current implementation handles this naturally because it checks:

if not node.left and not node.right:

This condition is true even for the root node.

Different Structures but Same Leaves

Two trees may have completely different internal layouts while still sharing identical leaf sequences. A buggy implementation might compare structure instead of leaves.

This solution avoids that issue entirely because it ignores non-leaf nodes during comparison and only stores leaf values.

Same Leaf Values in Different Orders

The order of leaves matters. For example:

[2, 3]

is different from:

[3, 2]

A flawed implementation using sets or sorted arrays would incorrectly treat these as equal.

This implementation preserves traversal order by always exploring the left subtree before the right subtree during DFS, ensuring the sequence remains accurate.