Same Tree Problem on LeetCode in Python

Spread the love

Introduction

Binary trees are widely used data structures with numerous applications, such as hierarchical data representation, expression trees, and decision-making models. Comparing binary trees is a fundamental operation for various applications, and understanding how to effectively accomplish this task is crucial. In this article, we will explore the “Same Tree” problem on LeetCode, understand the problem statement, and dive into different approaches to solve it using Python.

Table of Contents

  1. Introduction
  2. Understanding the Problem Statement
  3. Depth-First Approach (Recursive)
  4. Breadth-First Approach (Iterative)
  5. Time and Space Complexity Analysis
  6. Conclusion

Understanding the Problem Statement

The “Same Tree” problem on LeetCode is defined as follows:

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example:

Input: p = [1,2,3], q = [1,2,3]
Output: true
Input: p = [1,2], q = [1,null,2]
Output: false

In simpler terms, the problem requires us to check if the two given binary trees are identical both in structure and values of each node.

Depth-First Approach (Recursive)

A natural way to compare two trees is through a depth-first search. In this recursive approach, we check the current nodes’ values and recursively check the left subtree and the right subtree. If all the nodes match through this traversal, the trees are the same.

Here’s what the Python code looks like:

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

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # Both nodes are None, trees are same upto this point
        if not p and not q:
            return True
        
        # One of the nodes is None, trees are different
        if not p or not q:
            return False
        
        # Check the value of nodes and recursively check left and right subtrees
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Breadth-First Approach (Iterative)

While recursion offers a concise solution, the function call stack could become a limitation for extremely deep trees. An alternative approach is using an iterative breadth-first search. We can use a queue to keep track of nodes to be compared. While the queue is not empty, we dequeue nodes from both trees, compare them, and enqueue their children.

Here’s the Python code for this approach:

from collections import deque

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # Queue for Breadth-First Search
        queue = deque([(p, q)])
        
        while queue:
            node1, node2 = queue.popleft()
            
            # If both nodes are None, continue to next iteration
            if not node1 and not node2:
                continue
            
            # If only one of the nodes is None, trees are different
            if not node1 or not node2:
                return False
            
            # If the values are different, trees are different
            if node1.val != node2.val:
                return False
            
            # Enqueue children of both nodes
            queue.append((node1.left, node2.left))
            queue.append((node1.right, node2.right))
        
        return True

Time and Space Complexity Analysis

  1. Depth-First Approach (Recursive): The time complexity is O(n), where n is the number of nodes, as each node is visited once. The space complexity is O(h), where h is the height of the tree, accounting for the function call stack in recursion.
  2. Breadth-First Approach (Iterative): The time complexity is also O(n) as each node is processed once. The space complexity is O(w), where w is the maximum width of the tree, accounting for the queue storage.

Conclusion

In this article, we explored the “Same Tree” problem on LeetCode and discussed two main approaches in Python: the depth-first recursive approach and the breadth-first iterative approach. Both approaches have their merits, and choosing between them depends on the specific use case and constraints. Understanding these fundamental tree comparison techniques is crucial, as they form the building blocks for more complex tree-based algorithms and applications.

Leave a Reply