# Leaf-Similar Trees
**Difficulty:** EASY
[External](https://leetcode.com/problems/leaf-similar-trees)
Canonical: https://scaleengineer.com/dsa/problems/leaf-similar-trees
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake)
---
## Problem
Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a **leaf value sequence**_._

![](https://assets.glich.co/dsa/leaf-similar-trees/image0.png)

For example, in the given tree above, the leaf value sequence is `(6, 7, 4, 9, 8)`.

Two binary trees are considered _leaf-similar_ if their leaf value sequence is the same.

Return `true` if and only if the two given trees with head nodes `root1` and `root2` are leaf-similar.

**Example 1:**

![](https://assets.glich.co/dsa/leaf-similar-trees/image1.jpg) 

**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]
**Output:** true

**Example 2:**

![](https://assets.glich.co/dsa/leaf-similar-trees/image2.jpg) 

**Input:** root1 = [1,2,3], root2 = [1,3,2]
**Output:** false

**Constraints:**

* The number of nodes in each tree will be in the range `[1, 200]`.
* Both of the given trees will have values in the range `[0, 200]`.

# Approaches
## Depth-First Search with List Storage
This approach involves performing a Depth-First Search (DFS) on each tree to collect all its leaf values into a list. After traversing both trees and populating two separate lists with their respective leaf value sequences, the two lists are compared to check for equality.
**Time:** O(N1 + N2), where N1 and N2 are the number of nodes in the first and second trees, respectively. We must visit every node in both trees to find all the leaves. Comparing the two lists of leaves also takes time proportional to their lengths, which is at most O(N1 + N2). · **Space:** O(L1 + L2 + H1 + H2), where L1 and L2 are the number of leaves, and H1 and H2 are the heights of the trees. The space is used to store the leaf value sequences in lists (O(L1 + L2)) and for the recursion call stack (O(H1 + H2)). In the worst case of skewed trees, this becomes O(N1 + N2).
**Pros:** Simple and intuitive to implement.; The logic is straightforward, separating the leaf-finding from the comparison.
**Cons:** Uses significant extra space to store the entire leaf sequences, which can be large.; It traverses both trees completely, even if a mismatch is found early in the leaf sequence.
### Explanation
We define a helper function, say `getLeaves`, that takes a tree node and a list as input. This function will traverse the tree starting from the given node.
The traversal can be pre-order, in-order, or post-order; the key is to visit children in a consistent order (left then right) to maintain the left-to-right sequence of leaves.
Inside the `getLeaves` function, we check if the current node is a leaf (i.e., it has no left and no right child). If it is, we add its value to the list.
The main function `leafSimilar` initializes two empty lists. It then calls `getLeaves` for `root1` and the first list, and then for `root2` and the second list.
Finally, it compares the two populated lists. If they are identical in content and order, the trees are leaf-similar, and we return `true`; otherwise, `false`.
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leaves1 = new ArrayList<>();
        List<Integer> leaves2 = new ArrayList<>();
        getLeaves(root1, leaves1);
        getLeaves(root2, leaves2);
        return leaves1.equals(leaves2);
    }

    private void getLeaves(TreeNode node, List<Integer> leafValues) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            leafValues.add(node.val);
        }
        getLeaves(node.left, leafValues);
        getLeaves(node.right, leafValues);
    }
}
```
### Algorithm
- Initialize two empty lists, `leaves1` and `leaves2`.
- Define a recursive DFS helper function `getLeaves(node, list)`.
- In `getLeaves`, if `node` is null, return.
- If `node` is a leaf (`node.left == null && node.right == null`), add `node.val` to the `list`.
- Recursively call `getLeaves` for the left child: `getLeaves(node.left, list)`.
- Recursively call `getLeaves` for the right child: `getLeaves(node.right, list)`.
- Call `getLeaves(root1, leaves1)` to populate the first list.
- Call `getLeaves(root2, leaves2)` to populate the second list.
- Return the result of comparing `leaves1` and `leaves2` for equality.

## Space-Optimized Iterative DFS
This approach avoids storing the entire leaf sequences by comparing leaves one by one as they are found. It uses an iterative Depth-First Search (DFS) with a stack to simulate a generator that yields the next leaf of a tree. By running two such 'generators' in parallel, one for each tree, we can fetch and compare leaves on the fly.
**Time:** O(N1 + N2). Although it can terminate early, in the worst case (when the trees are leaf-similar or the mismatch occurs late), we still need to traverse all nodes of both trees. Each node is pushed and popped from its stack once. · **Space:** O(H1 + H2), where H1 and H2 are the maximum heights of the two trees. The space is dominated by the stacks used for the iterative DFS. This is a significant improvement over the first approach, especially for balanced trees where H is O(log N).
**Pros:** Highly space-efficient, using space proportional to the tree height rather than the number of nodes or leaves.; More time-efficient in practice for non-similar trees, as it can terminate as soon as the first mismatch is found.
**Cons:** The implementation is more complex than the simple recursive approach.; Managing the state of the traversal with an explicit stack can be less intuitive.
### Explanation
Instead of a recursive DFS, we use a stack for an iterative pre-order traversal. This allows us to 'pause' the traversal after finding a leaf and 'resume' it later to find the next one.
We create a helper function, `findNextLeaf`, which takes a stack (representing the state of the traversal for one tree) and finds the next leaf value.
The `findNextLeaf` function works in a loop: it pops a node from the stack. If the node is a leaf, its value is returned. If it's not a leaf, its children are pushed onto the stack (right child first, then left child) to ensure the left-to-right pre-order traversal.
The main function `leafSimilar` initializes two stacks, one for each tree, pushing the respective roots.
It then enters a loop, calling `findNextLeaf` for both stacks in each iteration to get the next pair of leaves.
If the leaf values differ, it immediately returns `false`. If one sequence ends before the other, it also returns `false`. If both sequences end at the same time (both `findNextLeaf` calls indicate no more leaves), it returns `true`.
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        if (root1 != null) s1.push(root1);
        if (root2 != null) s2.push(root2);
        
        while (!s1.isEmpty() && !s2.isEmpty()) {
            if (findNextLeaf(s1) != findNextLeaf(s2)) {
                return false;
            }
        }
        
        return s1.isEmpty() && s2.isEmpty();
    }

    private int findNextLeaf(Stack<TreeNode> stack) {
        while (true) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.left == null && node.right == null) {
                return node.val;
            }
        }
    }
}
```
### Algorithm
- Initialize two stacks, `s1` and `s2`, and push `root1` and `root2` onto them, respectively.
- Create a helper function `findNextLeaf(stack)` that finds and returns the value of the next leaf.
- Inside `findNextLeaf`, loop while the stack is not empty:
    - Pop a `node` from the stack.
    - If the `node` has a right child, push it onto the stack.
    - If the `node` has a left child, push it onto the stack. (This order ensures left-to-right traversal).
    - If the `node` is a leaf, return its value.
- In the main function, loop while both `s1` and `s2` are not empty.
- Inside the loop, call `findNextLeaf(s1)` and `findNextLeaf(s2)` and compare their results. If they are not equal, return `false`.
- After the loop, check if both stacks are empty. If they are, it means both leaf sequences were identical and have been fully traversed. Return `true`. Otherwise, one sequence was longer than the other, so return `false`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean leafSimilar ( TreeNode root1 , TreeNode root2 ) { List < Integer > l1 = dfs ( root1 ); List < Integer > l2 = dfs ( root2 ); return l1 . equals ( l2 ); } private List < Integer > dfs ( TreeNode root ) { if ( root == null ) { return new ArrayList <>(); } List < Integer > ans = dfs ( root . left ); ans . addAll ( dfs ( root . right )); if ( ans . isEmpty ()) { ans . add ( root . val ); } return ans ; } }
```

### JavaScript

```javascript
var leafSimilar = function ( root1 , root2 ) { const dfs = root => { if ( ! root ) { return []; } let ans = [... dfs ( root . left ), ... dfs ( root . right )]; if ( ! ans . length ) { ans = [ root . val ]; } return ans ; }; const l1 = dfs ( root1 ); const l2 = dfs ( root2 ); return l1 . toString () === l2 . toString (); };
```

### CPP

```cpp
/** * 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 ) { return dfs ( root1 ) == dfs ( root2 ); } vector < int > dfs ( TreeNode * root ) { if ( ! root ) return {}; auto ans = dfs ( root -> left ); auto right = dfs ( root -> right ); ans . insert ( ans . end (), right . begin (), right . end ()); if ( ans . empty ()) ans . push_back ( root -> val ); return ans ; } };
```

### Python

```python
# 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 dfs ( root ): if root is None : return [] ans = dfs ( root . left ) + dfs ( root . right ) return ans or [ root . val ] return dfs ( root1 ) == dfs ( root2 )
```