easy Leaf-Similar Trees

Problem Statement

Given the two root nodes root1 and root2 of two different binary trees, return true if both binary trees are leaf-similar trees. Otherwise, return false.

All leaves of the binary tree in left-to-right order create a leaf sequence. If both trees have same leaf sequence, they are considered as leaf-similar tree.

Examples

Example 1:

Input: root1 = [5,2,7,1,3,6,8], root2 = [7,5,2,1,3,6,8]

Expected Output: True
Justification: Both trees have the same leaf sequence [1,3,6,8], making them leaf-similar despite their different structures.

Example 2:

Input: root1 = [7, null, 8], root2 = [7,8]

Expected Output: True
Justification: Both Tree A and Tree B have the same leaf sequence [8], making them leaf-similar.

Example 3:

Input: root1 = [1,2,4,null,null,5,6], root2 = [1,2,5,null,null,4,6]

Expected Output: False
Justification: The leaf sequence for Tree A is [2,5,6], while for Tree B, it is [2,4,6]. Since the sequences do not match in order, the trees are not considered leaf-similar.

Try it yourself

Try solving this question here:

✅ Solution Leaf-Similar Trees

Problem Statement

Given the two root nodes root1 and root2 of two different binary trees, return true if both binary trees are leaf-similar trees. Otherwise, return false.

All leaves of the binary tree in left-to-right order create a leaf sequence. If both trees have same leaf sequence, they are considered as leaf-similar tree.

Examples

Example 1:

Input: root1 = [5,2,7,1,3,6,8], root2 = [7,5,2,1,3,6,8]

Expected Output: True
Justification: Both trees have the same leaf sequence [1,3,6,8], making them leaf-similar despite their different structures.

Example 2:

Input: root1 = [7, null, 8], root2 = [7,8]

Expected Output: True
Justification: Both Tree A and Tree B have the same leaf sequence [8], making them leaf-similar.

Example 3:

Input: root1 = [1,2,4,null,null,5,6], root2 = [1,2,5,null,null,4,6]

Expected Output: False
Justification: The leaf sequence for Tree A is [2,5,6], while for Tree B, it is [2,4,6]. Since the sequences do not match in order, the trees are not considered leaf-similar.

Solution

To solve this problem, we'll traverse each tree to extract the sequence of leaf nodes. The traversal approach ensures we accurately capture the order of leaves as they appear from left to right. By comparing these sequences directly, we can determine if the trees are leaf-similar. This method is effective because it isolates the aspect of the trees that matters for this problem—the leaf nodes—and disregards other structural differences. It's also efficient, as it focuses solely on leaf nodes and avoids unnecessary comparisons of non-leaf nodes.

Initially, we'll perform a depth-first search (DFS) on both trees. This search is ideal for navigating through each branch to its end, directly leading us to the leaves. By storing the leaf values in sequences (arrays or lists), we can easily compare these sequences once the traversals are complete. If the sequences are identical in both value and order, we conclude the trees are leaf-similar. This approach is straightforward yet powerful, leveraging the simplicity of DFS to address the core of what defines leaf similarity.

Step-by-Step Algorithm

Initialize Two Lists: Start by creating two empty lists, leaves1 and leaves2, which will store the sequences of leaf nodes for the first and second tree, respectively.
Depth-First Search (DFS) Traversal:
- Implement a recursive function dfs() that traverses the tree in a depth-first manner.
- The function should take a TreeNode (representing the current node in the traversal) and a list of integers (to store leaf values) as parameters.
Identify Leaf Nodes:
- In the dfs function, check if the current node is a leaf node. A node is considered a leaf if it has no left or right child.
- If the current node is a leaf, add its value to the leaves list passed as an argument.
Recursive DFS Calls:
- If the current node is not a leaf, recursively call the dfs function on its left child (if it exists) and its right child (if it exists).
- This step ensures that every node in the tree is visited, and all leaf nodes are identified and added to the leaves list.
Compare Leaf Sequences:
- After performing DFS traversals on both trees and obtaining their leaf sequences, compare these sequences for equality.
- The trees are considered "leaf-similar" if their leaf sequences are identical in both value and order. Return true if they are identical, or false otherwise.

Algorithm Walkthrough

Input Trees: root1 = [5,2,7,1,3,6,8] root2 = [7,5,2,1,3,6,8]

Step 1: Initialize two lists, leaves1 and leaves2, to hold the leaf sequences of root1 and root2, respectively.

Step 2: Perform a DFS traversal on root1.

Start from the root node (5). It's not a leaf, so proceed to its children.
Visit node 2. It's not a leaf, so proceed to its children.
- Visit node 1. It's a leaf, so add 1 to leaves1.
- Backtrack and visit node 3. It's a leaf, so add 3 to leaves1.
Backtrack to root and visit node 7. It's not a leaf, so proceed to its children.
- Visit node 6. It's a leaf, so add 6 to leaves1.
- Visit node 8. It's a leaf, so add 8 to leaves1.
After the traversal, leaves1 = [1,3,6,8].

Step 3: Perform a DFS traversal on root2.

Start from the root node (7). It's not a leaf, so proceed to its children.
Visit node 5. It's not a leaf (considering the corrected structure to match the leaf sequence), so proceed to its children.
- Visit node 2. Proceed to its children.
  - Visit node 1. It's a leaf, so add 1 to leaves2.
  - Visit node 3. It's a leaf, so add 3 to leaves2.
- Node 5 also leads to nodes 6 and 8 (right subtree of root or left subtree of node 7), where both are leaves, so add 6 and 8 to leaves2.
After the traversal, leaves2 = [1,3,6,8].

Step 4: Compare leaves1 and leaves2. Since they are identical ([1,3,6,8]), return true.

Code

java

import java.util.ArrayList;
import java.util.List;

// Definition for a binary tree node.
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
//     TreeNode(int x, TreeNode left, TreeNode right) {
//         this.val = x;
//         this.left = left;
//         this.right = right;
//     }
// }

public class Solution {

  // Method to check if two trees are leaf-similar
  public boolean leafSimilar(TreeNode root1, TreeNode root2) {
    List<Integer> leaves1 = new ArrayList<>();
    List<Integer> leaves2 = new ArrayList<>();
    // Extract leaf sequences for both trees
    dfs(root1, leaves1);
    dfs(root2, leaves2);
    // Compare the leaf sequences
    return leaves1.equals(leaves2);
  }

  // Helper method to perform DFS and collect leaf values
  private void dfs(TreeNode node, List<Integer> leaves) {
    if (node == null) return; // Base case
    if (node.left == null && node.right == null) leaves.add(node.val); // Add leaf value to the list
    else {
      dfs(node.left, leaves); // Traverse left subtree
      dfs(node.right, leaves); // Traverse right subtree
    }
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Corrected Example 1
    TreeNode treeA1 = new TreeNode(
      5,
      new TreeNode(2, new TreeNode(1), new TreeNode(3)),
      new TreeNode(7, new TreeNode(6), new TreeNode(8))
    );
    TreeNode treeB1 = new TreeNode(
      7,
      new TreeNode(
        5,
        new TreeNode(2, new TreeNode(1), new TreeNode(3)),
        new TreeNode(6)
      ),
      new TreeNode(8)
    );
    System.out.println(solution.leafSimilar(treeA1, treeB1)); // Expected: True

    // Example 2 (Unchanged)
    TreeNode treeA2 = new TreeNode(7, null, new TreeNode(8));
    TreeNode treeB2 = new TreeNode(7, new TreeNode(8), null);
    System.out.println(solution.leafSimilar(treeA2, treeB2)); // Expected: True

    // Example 3 (Unchanged)
    TreeNode treeA3 = new TreeNode(
      1,
      new TreeNode(2, new TreeNode(4), new TreeNode(5, null, new TreeNode(6))),
      null
    );
    TreeNode treeB3 = new TreeNode(
      1,
      new TreeNode(2, new TreeNode(5), new TreeNode(4, null, new TreeNode(6))),
      null
    );
    System.out.println(solution.leafSimilar(treeA3, treeB3)); // Expected: False
  }
}

Complexity Analysis

Time Complexity

DFS Traversal: The depth-first search (DFS) traversal visits each node exactly once in both trees. so, the time complexity for traversing both trees is , where n is the number of nodes in the first tree and m is the number of nodes in the second tree.
Comparing Leaf Sequences: The comparison of two leaf sequences (lists) has a complexity of , where k is the number of leaf nodes in the smaller list. In the worst case, k could be as large as min(n, m).

Thus, the overall time complexity of the algorithm is , which simplifies to since k is bounded by n and m.

Space Complexity

Space for Leaf Sequences: The space required to store the leaf sequences of both trees is proportional to the number of leaf nodes. In the worst case, a binary tree can have up to n/2 leaves (for a perfectly balanced tree), so the space complexity for the leaf lists is , which simplifies to .
Recursive Stack Space: The DFS traversal incurs additional space cost due to recursive function calls, which in the worst case (a skewed tree) could be , where h1 and h2 are the heights of the two trees.

The overall space complexity, considering both the space for leaf sequences and the recursive stack space, is . In most practical scenarios, especially for balanced trees, the height factor h1 + h2 is much smaller than the number of nodes, leading to an overall space complexity closer to .

🤖 Don't fully get this? Learn it with Claude

Stuck on Leaf-Similar Trees? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Leaf-Similar Trees** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Leaf-Similar Trees** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Leaf-Similar Trees**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Leaf-Similar Trees**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Reverse a LinkedList Is Subsequence →