Code Implementation

# 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: TreeNode, root2: TreeNode) -> bool:
        def dfs(node, leaves):
            if node is None:
                return
            if node.left is None and node.right is None:
                leaves.append(node.val)
            dfs(node.left, leaves)
            dfs(node.right, leaves)
        
        leaves1, leaves2 = [], []
        dfs(root1, leaves1)
        dfs(root2, leaves2)
        return leaves1 == leaves2
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };
class Solution {
public:
    void dfs(TreeNode* node, vector<int>& leaves) {
        if (!node) return;
        if (!node->left && !node->right) {
            leaves.push_back(node->val);
        }
        dfs(node->left, leaves);
        dfs(node->right, leaves);
    }
    
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> leaves1, leaves2;
        dfs(root1, leaves1);
        dfs(root2, leaves2);
        return leaves1 == leaves2;
    }
};
      

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }
class Solution {
    private void dfs(TreeNode node, List<Integer> leaves) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            leaves.add(node.val);
        }
        dfs(node.left, leaves);
        dfs(node.right, leaves);
    }
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leaves1 = new ArrayList<>();
        List<Integer> leaves2 = new ArrayList<>();
        dfs(root1, leaves1);
        dfs(root2, leaves2);
        return leaves1.equals(leaves2);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function(root1, root2) {
    function dfs(node, leaves) {
        if (!node) return;
        if (!node.left && !node.right) {
            leaves.push(node.val);
        }
        dfs(node.left, leaves);
        dfs(node.right, leaves);
    }
    const leaves1 = [], leaves2 = [];
    dfs(root1, leaves1);
    dfs(root2, leaves2);
    return JSON.stringify(leaves1) === JSON.stringify(leaves2);
};
      

Problem Description

Given two binary trees, root1 and root2, determine if they are leaf-similar. Two binary trees are considered leaf-similar if their leaf value sequence is the same when traversed from left to right.

The leaf value sequence is the sequence of values of all leaf nodes (nodes with no children) as they appear from leftmost leaf to rightmost leaf.

• Both trees are non-empty.
• Each tree node contains an integer value.
• You need to compare the sequence of leaf values, not the tree structure.
• The order of leaves matters, and all leaves must match in both value and order for the trees to be leaf-similar.

Thought Process

Before jumping into code, let's think about how to solve this problem. The main task is to compare the sequence of leaf nodes from two trees. At first glance, a brute-force approach might involve traversing both trees, collecting all their leaves, and then comparing the two sequences.

The key insight is that we don't care about the overall tree structure, only the sequence of leaf values. This means we can ignore non-leaf nodes and just focus on collecting leaf values in the correct order.

To optimize, we can use a depth-first search (DFS) to traverse each tree and collect the leaf values as we encounter them. Once we have both sequences, we simply compare them for equality.

This approach is both simple and efficient, as it only requires a single traversal of each tree and a comparison of two lists.

Solution Approach

• Step 1: Traverse Each Tree
  • Use a helper function (typically a recursive DFS) to traverse each tree.
  • During the traversal, when we encounter a node that has no left or right children, we know it's a leaf node.
  • We add the value of each leaf node to a list (or array).
• Step 2: Collect Leaf Sequences
  • For both root1 and root2, collect their leaf sequences using the traversal function.
• Step 3: Compare the Sequences
  • After both sequences are collected, compare them directly (using == in Python, equals() in Java, etc.).
  • If the sequences are identical (same values, same order), return true. Otherwise, return false.

We use a list because it preserves the order of leaf values as we traverse the tree from left to right. DFS is a natural fit for tree traversal and allows us to easily identify and collect leaves.

Example Walkthrough

Let's consider the following example:

Tree 1:
    3
  /    \
5      1
/ \    / \
6 2  9 8
/ \
7 4

Tree 2:
    3
  /    \
5      1
/ \    / \
6 7  4 2
    / \
9 8

Step-by-step:

• Traverse Tree 1: The leaf sequence is [6, 7, 4, 9, 8]
• Traverse Tree 2: The leaf sequence is [6, 7, 4, 9, 8]
• Compare the two sequences: They are the same, so the trees are leaf-similar.

If the sequences had differed in either value or order, the result would be false.

Time and Space Complexity

• Brute-force Approach:
  • Traverse each tree and collect all nodes, then filter out the leaves. This would be O(N) time, but with unnecessary extra steps.
• Optimized Approach (used here):
  • Time Complexity: O(N + M), where N and M are the number of nodes in the two trees. Each node is visited once.
  • Space Complexity: O(L1 + L2), where L1 and L2 are the number of leaves in each tree, since we store the leaf sequences. The recursion stack can add up to O(H), where H is the height of the tree, but in the worst case (skewed tree) that's O(N).

The approach is efficient because we only store and compare what's necessary: the leaf sequences.

Summary

To determine if two binary trees are leaf-similar, we collect the sequence of their leaf node values using a simple depth-first traversal. By comparing these sequences, we can quickly and efficiently decide if the trees meet the leaf-similar condition. The solution is elegant because it reduces the problem to a simple list comparison after traversing each tree just once, making it both easy to implement and efficient.