Solution: Leaf-Similar Trees

Grokking Amazon Coding Interview

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Leaf-Similar Trees

Table of Contents

Contents are not accessible

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

Python3

. . . .

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 $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.
Comparing Leaf Sequences: The comparison of two leaf sequences (lists) has a complexity of $O(k)$ , 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 $O(n + m + k)$ , which simplifies to $O(n + m)$ 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 $O(n/2 + m/2)$ , which simplifies to $O(n + m)$ .
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 $O(h1 + h2)$ , 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 $O(n + m + h1 + h2)$ . 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 $O(n + m)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible