We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Leaf-Similar Trees

Number: 904

Difficulty: Easy

Paid? No

Companies: Meta, Microsoft, Amazon, Google

Problem Description

Given two binary trees, determine if they are leaf-similar. Two trees are considered leaf-similar if their leaf value sequence (the values of the leaves from left to right) is the same.

Key Insights

  • Collect the leaf values from each tree in a left-to-right order.
  • Use Depth-First Search (DFS) to traverse the trees recursively and gather only the leaf node values.
  • Compare the two resulting leaf value lists; if they are identical, the trees are leaf-similar.

Space and Time Complexity

Time Complexity: O(n) for each tree, where n is the number of nodes; overall O(n1 + n2). Space Complexity: O(n) for storing the leaf values and potential recursion stack.

Solution

We can solve the problem by performing a DFS traversal on each tree to collect the leaf nodes. A leaf is defined as a node with no left or right children. After collecting the leaf nodes from both trees in order, we simply compare the two lists. Key data structures:

  • Arrays (or lists) to store the sequence of leaf values.
  • Recursion stack for the DFS algorithm. Algorithmic approach:
  1. Define a helper function that traverses the tree recursively.
  2. When a leaf node is encountered (both left and right child are null), add its value to the list.
  3. Compare the two resulting lists from each tree. If they are identical, return true; otherwise, return false.

Code Solutions

# 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: TreeNode, root2: TreeNode) -> bool:
        # Helper function to perform DFS and collect leaf values
        def dfs(node, leaves):
            if node:
                # Check if it is a leaf node
                if not node.left and not node.right:
                    leaves.append(node.val)
                # Recursively search left subtree
                dfs(node.left, leaves)
                # Recursively search right subtree
                dfs(node.right, leaves)
        # Initialize lists to store leaf sequences from both trees
        leaves1 = []
        leaves2 = []
        dfs(root1, leaves1)
        dfs(root2, leaves2)
        # Return true if both leaf sequences are identical
        return leaves1 == leaves2
← Back to All Questions