Leaf-Similar Trees

Easy · Graphs · Explanation and code example

Iterative DFS

How it works

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.

Steps

  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).

Complexity

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

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

Things to watch for

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.

Python code example

from typing import Optional

# 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

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        stack<TreeNode*> stack1, stack2;
        stack1.push(root1);
        stack2.push(root2);

        while (!stack1.empty() && !stack2.empty()) {
            if (getPathLeaf(stack1) != getPathLeaf(stack2)) {
                return false;
            }
        }
        return stack1.empty() && stack2.empty();
    }

private:
    int getPathLeaf(stack<TreeNode*>& stack) {
        while (!stack.empty()) {
            TreeNode* node = stack.top();
            stack.pop();
            if (node->right) {
                stack.push(node->right);
            }
            if (node->left) {
                stack.push(node->left);
            }
            if (!node->left && !node->right) {
                return node->val;
            }
        }
        return -1;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations