algoadvance

Consider all the leaves of a binary tree from left to right order form a leaf value sequence. For example, in the given tree:

    3
   / \
  5   1
 / \ / \
6  2 9  8
  / \
 7   4

The leaf value sequence is [6, 7, 4, 9, 8].

Two binary trees are considered leaf-similar if their leaf value sequence is the same, even if the structure of the trees is different.

Write a function to determine if two given binary trees are leaf-similar. The trees will be provided in the form of their root nodes.

Clarifying Questions:

1. What form does the input take?
   • The input consists of two root nodes of the two binary trees.
2. Can the trees be empty?
   • Yes, and two empty trees would be considered leaf-similar.
3. How are tied structures where there are no leaves handled?
   • For non-leaf nodes, we don’t care about their specific values.
4. What should the function return?
   • The function should return True if the leaf sequences are the same, and False otherwise.

Code:

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

def leafSimilar(root1: TreeNode, root2: TreeNode) -> bool:
    
    def get_leaf_sequence(root):
        if not root:
            return []
        leaves = []
        
        def dfs(node):
            if not node:
                return
            if not node.left and not node.right:
                leaves.append(node.val)
            dfs(node.left)
            dfs(node.right)
        
        dfs(root)
        return leaves
    
    return get_leaf_sequence(root1) == get_leaf_sequence(root2)

# Example usage:
# tree1 = TreeNode(3)
# tree1.left = TreeNode(5)
# tree1.right = TreeNode(1)
# tree1.left.left = TreeNode(6)
# tree1.left.right = TreeNode(2)
# tree1.left.right.left = TreeNode(7)
# tree1.left.right.right = TreeNode(4)
# tree1.right.left = TreeNode(9)
# tree1.right.right = TreeNode(8)

# tree2 = TreeNode(3)
# tree2.left = TreeNode(5)
# tree2.right = TreeNode(1)
# tree2.left.left = TreeNode(6)
# tree2.left.right = TreeNode(2)
# tree2.left.right.left = TreeNode(7)
# tree2.left.right.right = TreeNode(4)
# tree2.right.left = TreeNode(9)
# tree2.right.right = TreeNode(8)

# print(leafSimilar(tree1, tree2)) # Output: True

Strategy:

1. Extract Leaf Sequences:
   • We defined a function get_leaf_sequence that extracts the leaf nodes of a tree in left-to-right order.
2. Depth-First Search (DFS):
   • A DFS traversal is used to find leaf nodes. If a node has no children, it is a leaf node.
3. Compare Sequences:
   • Compare the leaf sequences of both trees to determine if they are similar.

Time Complexity:

• Time Complexity: O(N1 + N2), where N1 and N2 are the number of nodes in the first and second tree, respectively. This is because each node is visited once in the DFS traversal.
• Space Complexity: O(H1 + H2), where H1 and H2 are the heights of the two trees. This is due to the maximum depth of recursive calls in the DFS. In the worst case (a completely unbalanced tree), this could be as large as O(N), but in the average case, it is O(log N) for balanced trees.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?