Leaf-Similar Trees — Solution in Python, Java & C++
Leaf-Similar Trees solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Leaf-Similar Trees is an easy coding problem on depth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Read the leaves of a binary tree (the nodes with no children) from left to right: that sequence of values is the tree's leaf value sequence.
Given the roots of two binary trees root1 and root2, return true if their leaf value sequences are identical, and false otherwise. The two trees may have completely different shapes.
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]
Output: true
Explanation: Both trees read 6, 7, 4, 9, 8 along their leaves from left to right.
Example 2
Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false
Explanation: The leaves read 2, 3 in the first tree and 3, 2 in the second: same values, different order.
Example 3
Input: root1 = [1], root2 = [2,null,1]
Output: true
Explanation: A lone root is its own leaf. The second tree's only leaf is also 1.
Constraints
1 <= number of nodes in each tree <= 2000 <= Node.val <= 200
Hints for Leaf-Similar Trees
Hint 1
Only the leaves matter, and only their left-to-right order.
Hint 2
Any depth-first traversal that visits the left subtree before the right one meets the leaves in left-to-right order.
Hint 3
Collect each tree's leaves into a list and compare the two lists element by element (lengths included).
How to solve Leaf-Similar Trees
A depth-first traversal that always goes left before right reaches the leaves in exactly left-to-right order, so each tree's leaf sequence is one traversal away.
Approach
- Traverse the first tree depth-first (left before right), appending every node with no children to a list.
- Do the same for the second tree.
- Return whether the two lists are equal — same length and the same value at every position.
Why it works
In a preorder walk every node of a left subtree is visited before any node of the right subtree, at every level of the recursion, so two leaves are appended in the order they appear across the tree from left to right.
Complexity
- Time —
O(n1 + n2) - Space —
O(n1 + n2) for the two sequences and the traversal stacks
Pitfalls
- Comparing only the multiset of leaf values is wrong:
[1,2,3]and[1,3,2]hold the same leaves in a different order. - Push the right child before the left on an explicit stack, or the leaves come out right to left.
Reference solution
Python
from typing import List, Optional
def leafSimilar(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
return leaves(root1) == leaves(root2)
def leaves(root: Optional[TreeNode]) -> List[int]:
out = []
stack = [root] if root else []
while stack:
node = stack.pop()
if node.left is None and node.right is None:
out.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return outJava
public static boolean leafSimilar(TreeNode root1, TreeNode root2) {
return leaves(root1).equals(leaves(root2));
}
static List<Integer> leaves(TreeNode root) {
List<Integer> out = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.left == null && node.right == null) out.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return out;
}C++
vector<int> leaves(TreeNode* root);
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
return leaves(root1) == leaves(root2);
}
vector<int> leaves(TreeNode* root) {
vector<int> out;
vector<TreeNode*> stack;
if (root) stack.push_back(root);
while (!stack.empty()) {
TreeNode* node = stack.back();
stack.pop_back();
if (!node->left && !node->right) out.push_back(node->val);
if (node->right) stack.push_back(node->right);
if (node->left) stack.push_back(node->left);
}
return out;
}JavaScript
var leafSimilar = function(root1, root2) {
var a = leaves(root1), b = leaves(root2);
if (a.length !== b.length) return false;
for (var i = 0; i < a.length; i++) if (a[i] !== b[i]) return false;
return true;
};
var leaves = function(root) {
var out = [], stack = root === null ? [] : [root];
while (stack.length > 0) {
var node = stack.pop();
if (node.left === null && node.right === null) out.push(node.val);
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals