872. Leaf-Similar Trees
Problem Description
In the given problem, we are asked to compare two binary trees to check if they are 'leaf-similar'. Binary trees are a type of data structure in which each node has at most two children, referred to as the left child and the right child. A leaf node is a node with no children. The 'leaf value sequence' is the list of values of these leaf nodes read from left to right. Two binary trees are considered 'leaf-similar' if the sequences of their leaf values are identical.
For example, the leaf value sequence of the tree depicted in the problem is (6, 7, 4, 9, 8)
as those are the values of the nodes that have no children, read from left to right. To solve this problem, we need to collect the leaf sequences from both trees and then compare them to determine if the two trees are 'leaf-similar'.
Flowchart Walkthrough
Let's analyze the Leetcode problem 872, Leaf-Similar Trees, using the Flowchart. Here's how to proceed step-by-step:
-
Is it a graph?
- Yes: Despite being about trees, each tree can be considered a graph.
-
Is it a tree?
- Yes: Specifically, the problem deals with comparing leaf sequences from two binary trees.
-
Conclusion: According to the flowchart, once we determine that the structure in question is a tree, the recommended approach is to use Depth-First Search (DFS) to traverse and process the trees. In the context of this problem, DFS would be appropriate for efficiently visiting each leaf in the given binary trees to compare their leaf sequences.
Intuition
To solve this problem, we can use a Depth-First Search (DFS) on both trees. DFS is an algorithm for traversing or searching tree or graph data structures. In the context of a binary tree, it starts at the root and explores as far as possible along each branch before backtracking.
Here's why DFS is suitable for this problem:
- DFS can be easily implemented using recursion.
- While traversing the tree using DFS, we have a clear path to the leaf nodes, which are the focus of this problem.
- We can build the leaf sequence during the DFS by adding the node's value to our sequence only when we hit a leaf node (a node with no children).
The provided solution uses the DFS method dfs
to traverse each tree starting from the root and collect the leaves values. The function dfs
recursively visits the left and right children of the current node and stores the node's value if and only if the node is a leaf (i.e., it has neither a left nor a right child). This collected sequence of values is then returned as a list for each tree. Finally, the solution compares the two lists of leaf values, and if they are equal, it returns true
, indicating the two trees are leaf-similar. If not, it returns false
.
Learn more about Tree, Depth-First Search and Binary Tree patterns.
Solution Approach
The solution is implemented in Python, and it focuses on a Depth-First Search (DFS) approach to traverse through the binary trees. The implementation defines a nested function dfs
within the leafSimilar
method, with the purpose of performing the actual DFS traversal, searching the entire tree for its leaves, and building the leaf sequence.
Here's the step-by-step breakdown of the algorithm:
- The
dfs
function is defined, which takes a single argument,root
, representing the current node in the tree. - Upon each invocation of
dfs
, the function first checks if the currentroot
node isNone
. If it is, it returns an empty list as there are no leaves to gather from aNone
subtree. - If the current node is not
None
, thedfs
function first recursively calls itself withroot.left
androot.right
to search through the entire left and right subtrees. - The leaves are gathered by this part of the code:
ans = dfs(root.left) + dfs(root.right)
. This code concatenates the left and right subtree leaves into one sequence. - Finally, the function checks if the node is a leaf node, that means both
root.left
androot.right
areNone
. If it is a leaf, it returns a list containing the leaf's value:[root.val]
. If the node is not a leaf, it returns the concatenated list of leaf values from both the left and right subtrees. - The main function
leafSimilar
calls thedfs
function for bothroot1
androot2
trees, collecting the sequences of leaf values as lists. - The solution concludes by comparing these two lists with
dfs(root1) == dfs(root2)
. If they are identical, it means that the leaf value sequences are the same, and therefore the two trees are considered leaf-similar andTrue
is returned. If the sequences differ in any way, the function returnsFalse
.
This solution uses recursion as a natural way to navigate a tree's structure and gather leaf values, exploiting the divide-and-conquer nature of the problem. The code is efficient and concise, exploring each node exactly once, which results in a time complexity of O(N), where N is the total number of nodes in the tree.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take two small binary trees as an example to illustrate the solution approach:
Consider the following binary trees, Tree1
and Tree2
:
1 Tree1 Tree2 2 3 5 3 / \ / \ 4 5 1 3 6 5 / \ \ 6 6 2 7 7 / 8 7
For Tree1
, given the binary tree structure, the leaves are the nodes with the values 6
, 7
, and 1
. Therefore, the leaf value sequence for Tree1
is [6, 7, 1]
.
For Tree2
, the leaves are the nodes with the values 3
, 7
, and 6
. Thus, the leaf value sequence for Tree2
is [3, 7, 6]
.
Now we want to determine if Tree1
and Tree2
are leaf-similar according to the problem statement using the DFS approach.
Step-by-Step Walkthrough:
-
For
Tree1
, thedfs
function begins at the root node3
, and then recursively searches the left child5
. From node5
, it further traverses its children6
(a leaf node) and2
. The function finds leaf6
and continues to explore2
, down to leaf7
. -
Simultaneously, it explores the right child
1
of the root node3
which is also a leaf node. Here, thedfs
function collects the leaf value1
. The sequence forTree1
is now[6, 7, 1]
. -
For
Tree2
, thedfs
function starts at the root node5
, then traverses the left child3
. Node3
is a leaf so it records the value3
and stops moving further down this branch. -
Afterwards, it explores the right side of
5
, going down to6
which is a leaf node. It also records7
which is the left child leaf node of node6
. The sequence forTree2
is[3, 7, 6]
. -
After collecting the leaf sequences from both trees using DFS, the solution now compares the leaf value sequences of both trees:
[6, 7, 1]
forTree1
and[3, 7, 6]
forTree2
. -
Since the leaf sequences are not identical (since
[6, 7, 1]
is not the same as[3, 7, 6]
), our function will returnFalse
, indicating thatTree1
andTree2
are not leaf-similar.
Following this approach, we can see that the DFS algorithm efficiently finds the leaf sequences for both trees, and the comparison step at the end of the process is a simple equality check. This example demonstrates the solution approach on a smaller scale, which is directly applicable to larger and more complex tree structures.
Solution Implementation
1# Definition for a binary tree node.
2class TreeNode:
3 def __init__(self, val=0, left=None, right=None):
4 self.val = val
5 self.left = left
6 self.right = right
7
8class Solution:
9 def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
10 # Helper function to perform a depth-first search (DFS) to find all leaf values in order
11 def dfs(root):
12 # If the current node is None, return an empty list
13 if root is None:
14 return []
15
16 # Recursively explore the left and right children, and accumulate leaf values
17 leaves = dfs(root.left) + dfs(root.right)
18
19 # If 'leaves' is empty, it means this is a leaf node, so return its value
20 # Otherwise, it means this is an internal node and 'leaves' contains its subtree's leaves
21 return leaves or [root.val]
22
23 # Compare the leaf value sequences of both trees
24 return dfs(root1) == dfs(root2)
25
1// Class for the Solution containing the method to check if two binary trees are leaf-similar
2class Solution {
3 // Method to check if two given trees have leaves with the same sequence when traversed left-to-right
4 public boolean leafSimilar(TreeNode root1, TreeNode root2) {
5 // Perform DFS on both trees and store the leaf values
6 List<Integer> leavesOfTree1 = traverseAndCollectLeaves(root1);
7 List<Integer> leavesOfTree2 = traverseAndCollectLeaves(root2);
8
9 // Return the comparison result of leaves
10 return leavesOfTree1.equals(leavesOfTree2);
11 }
12
13 // Recursive method that performs DFS and collects leaf node's values
14 private List<Integer> traverseAndCollectLeaves(TreeNode node) {
15 // Base case: if the current node is null, return an empty list
16 if (node == null) {
17 return new ArrayList<>();
18 }
19
20 // Traverse the left subtree and collect its leaf nodes
21 List<Integer> leaves = traverseAndCollectLeaves(node.left);
22
23 // Traverse the right subtree and collect its leaf nodes
24 leaves.addAll(traverseAndCollectLeaves(node.right));
25
26 // Check if current node is a leaf node (as it will have no children after above traversals)
27 if (leaves.isEmpty()) {
28 // If it's a leaf, add its value to the list
29 leaves.add(node.val);
30 }
31
32 // Return the list of leaf node's values
33 return leaves;
34 }
35}
36
1#include <vector>
2
3// Definition for a binary tree node.
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode() : val(0), left(nullptr), right(nullptr) {}
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
11};
12
13class Solution {
14public:
15 // Method to check if two binary trees are leaf-similar.
16 bool leafSimilar(TreeNode* root1, TreeNode* root2) {
17 // Compare the leaf value sequence of two trees
18 return getLeafValues(root1) == getLeafValues(root2);
19 }
20
21 // Helper method to perform DFS and collect leaf nodes.
22 vector<int> getLeafValues(TreeNode* node) {
23 // Base case: if current node is null, return an empty vector.
24 if (!node) return {};
25
26 // Recurse on left subtree.
27 vector<int> leaves = getLeafValues(node->left);
28
29 // Recurse on right subtree and append its result to `leaves` vector.
30 vector<int> rightLeaves = getLeafValues(node->right);
31 leaves.insert(leaves.end(), rightLeaves.begin(), rightLeaves.end());
32
33 // If current node is a leaf node, add its value to `leaves` vector.
34 if (leaves.empty()) leaves.push_back(node->val);
35
36 return leaves;
37 }
38};
39
1// Define a basic structure for a TreeNode.
2class TreeNode {
3 val: number;
4 left: TreeNode | null;
5 right: TreeNode | null;
6
7 constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
8 this.val = val;
9 this.left = left;
10 this.right = right;
11 }
12}
13
14// Function to check if two binary trees are leaf-similar.
15// Returns true if they are leaf-similar, otherwise false.
16function leafSimilar(root1: TreeNode | null, root2: TreeNode | null): boolean {
17 // Compare the leaf value sequence of two trees
18 return getLeafValues(root1).toString() === getLeafValues(root2).toString();
19}
20
21// Helper function to perform DFS and collect leaf nodes.
22// Takes a node and returns an array of leaf values.
23function getLeafValues(node: TreeNode | null): number[] {
24 // Base case: if current node is null, return an empty array.
25 if (!node) return [];
26
27 // Recurse on left subtree.
28 let leaves: number[] = getLeafValues(node.left);
29
30 // Recurse on the right subtree and append its result to the 'leaves' array.
31 let rightLeaves: number[] = getLeafValues(node.right);
32 leaves = leaves.concat(rightLeaves);
33
34 // If the current node is a leaf, add its value to the 'leaves' array.
35 if (!node.left && !node.right) leaves.push(node.val);
36
37 return leaves;
38}
39
40// Usage Example:
41// const tree1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
42// const tree2 = new TreeNode(1, new TreeNode(3), new TreeNode(2));
43// console.log(leafSimilar(tree1, tree2)); // Outputs: false
44
Time and Space Complexity
The provided Python code defines a function leafSimilar
that takes the roots of two binary trees and returns True
if the trees are "leaf similar," which means they have the same sequence of leaf values when traversed in depth-first order.
Time Complexity
The time complexity of the algorithm is determined by the depth-first search (DFS) function, which visits every node in the binary tree exactly once. Therefore, the time complexity is O(N+M)
, where N
is the number of nodes in the first tree and M
is the number of nodes in the second tree.
The DFS function is applied to both trees separately, so we traverse every node of both trees once, leading to the combined time complexity.
Space Complexity
The space complexity is mainly governed by the call stack of the recursive DFS calls and the space used to store the leaf values. In the worst case, the depth of the recursion could be O(H1+H2)
, where H1
is the maximum height of the first tree and H2
is the maximum height of the second tree, if the trees are highly skewed.
Additionally, the space required to store the leaf values is equal to the total number of leaves in both trees. However, since the DFS function concatenates lists and returns them, if we consider the output as a part of the space complexity, it would be equal to the total number of nodes (like a post-order traversal), which in the worst case would be O(N+M)
, where both trees are full trees, and each node is stored in the list exactly once.
If the output space is not considered in the space complexity (which is common in analysis), then we mainly consider the space taken by the call stack, leading to the space complexity of O(H1+H2)
.
Thus, the space complexity of the algorithm depends on whether the output space is included, making it either O(H1+H2)
if not (recursive call stack only) or O(N+M)
if yes (including the output list).
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node