Leetcode – Leaf-Similar Trees Solution in Python

Spread the love

Trees are a fundamental data structure in computer science and are utilized to represent hierarchical structures. Operations and characteristics of trees often form the basis of many intriguing computational problems. One such captivating problem on Leetcode is the Leaf-Similar Trees problem. This article will provide a thorough exploration of the problem, including problem definition, insights, solution strategies, and Python implementations.

Problem Statement

Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.

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.

Constraints:

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

Examples:

1. Input:

Tree 1:   3
         / \
        5   1
       /|   |\
      6 2   9 8
        / \
       7   4
Tree 2:   3
         / \
        5   1
       /|   |\
      6 7   4 2
              / \
             9   8

Output: true

2. Input

Tree 1:   1
Tree 2:   1

Output: true

Analysis

From the problem statement, we gather that we need to traverse both trees and collect the leaf nodes in order. Then, we simply compare the two sequences to determine if the trees are leaf-similar.

The main challenge lies in the traversal strategy to ensure we efficiently capture all the leaf nodes.

Solution Strategy

  1. Depth-First Search (DFS): A depth-first traversal of the tree can help us capture the leaf nodes efficiently. As we traverse, every time we come across a leaf node (a node that doesn’t have left or right children), we append it to a list.
  2. After collecting the leaf nodes from both trees, we compare the two sequences to check for equality.

Python Code:

To understand the structure and methods of the binary tree, let’s define a basic tree node:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Now, let’s dive into the solution:

class Solution:
    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
        def dfs(node, leaf_sequence):
            if not node:
                return
            # If the node is a leaf node
            if not node.left and not node.right:
                leaf_sequence.append(node.val)
            dfs(node.left, leaf_sequence)
            dfs(node.right, leaf_sequence)

        leaves_tree1, leaves_tree2 = [], []
        dfs(root1, leaves_tree1)
        dfs(root2, leaves_tree2)

        return leaves_tree1 == leaves_tree2

Complexity Analysis

  1. Time Complexity: The depth-first search ensures that we visit each node in the trees once. So, the time complexity is O(N1 + N2), where N1 and N2 are the number of nodes in root1 and root2, respectively.
  2. Space Complexity: The primary space consumption is from the recursive stack (in a worst-case scenario when the tree is skewed, this can go up to O(N1 or N2)), and the space needed to store the leaf sequences for both trees, leading to a space complexity of O(N1 + N2).

Conclusion

The Leaf-Similar Trees problem is a brilliant representation of how tree traversal strategies can be applied to discern patterns and characteristics of binary trees. While the problem primarily hinges on a simple traversal and comparison, it exemplifies the significance of understanding tree properties and traversal techniques in tackling more complex tree-related problems. Combining depth-first traversal with the tree’s inherent hierarchical structure makes this challenge a great introduction to binary tree operations.

Leave a Reply