Same Tree Problem

A new day and a new leetcode problem. Today it's Same Tree Problem and it is an easy one but my intent here is to list out all the possible approaches to tackle this problem.

deepai.org

Problem Statement: 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.

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

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

Approach 1: Recursive approach
This approach compares the values of the current nodes and then recursively compares the left and right children of the nodes.

# 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Solution using recursion has a time complexity of O(N), where N is the number of nodes in the tree. This is because the algorithm visits each node in the tree exactly once and space complexity is O(H) where H is the height of the tree.

Approach 2: Breadth First Traversal (Or Level Order Traversal) or BFS
This approach uses a queue to keep track of the nodes to be processed and compares the values of the nodes as they are processed.

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        from collections import deque
        queue = deque([(p, q)])
        while queue:
            node1, node2 = queue.popleft()
            if node1 is None and node2 is None:
                continue
            if node1 is None or node2 is None:
                return False
            if node1.val != node2.val:
                return False
            queue.append((node1.left, node2.left))
            queue.append((node1.right, node2.right))
        return True

This implementation of BFS algorithm has a time complexity of O(N) where N is the number of nodes in the tree and the space complexity is O(N) where N is the number of nodes in the tree. This is because at any given time, the queue may contain all nodes in the tree.

Approach 3: Depth First Traversal or DFS
Depth-first search (DFS) is a method for traversing a tree or graph data structure in which a node is fully explored before moving on to the next node. The traversal can be done using any order such as pre-order, in-order or post-order.

Pre-order Traversal

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        def pre_order(node):
            if not node:
                return []
            return [node.val] + pre_order(node.left) + pre_order(node.right)
        
        return pre_order(p) == pre_order(q)

Post-order Traversal

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        def post_order(node):
            if not node:
                return []
            return post_order(node.left) + post_order(node.right) + [node.val]
        
        return post_order(p) == post_order(q)

In-order Traversal

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        def in_order(node):
            if not node:
                return []
            return in_order(node.left) + [node.val] + in_order(node.right)
        
        return in_order(p) == in_order(q)

The time complexity of DFS is O(N) where N is the number of nodes in the tree, as the function visits each node in the tree exactly once and The space complexity of DFS is O(H) where H is the height of the tree.

Approach 4: DFS but using an explicit stack
But why use an explicit stack? here is the answer given by ChatGPT:

“An explicit stack is used in the DFS algorithm when we implement it iteratively instead of recursively. In recursive approach, the function calls itself for each child of the current node and the call stack keeps track of the function calls, this is known as the call stack. However, when the tree is too deep, the call stack can grow too large and cause a stack overflow error.

An explicit stack is used as an alternative to the call stack. It allows us to manually control the order in which the nodes are visited, by pushing and popping the nodes from the stack. This can help to avoid stack overflow errors in case of deep tree, and also it is more efficient in terms of memory usage in situations where recursion depth is too big or recursion is not allowed.

Moreover, Using explicit stack gives more control over the order of nodes visiting, such as DFS can be implemented in various order such as pre-order, post-order and in-order.

It’s important to note that although explicit stack can help to avoid stack overflow errors, it also increases the space complexity of the algorithm to O(N) where N is the number of nodes in the tree, as the stack may contain all the nodes of the tree at some point.

In conclusion, it is mostly a matter of preference, if you are comfortable with recursion and don’t have a deep tree, you could use the recursive approach, but if you are more comfortable with explicit stack usage or recursion depth is too big, using explicit stack is a good option.”

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        stack = [(p, q)]
        while stack:
            node1, node2 = stack.pop()
            if node1 is None and node2 is None:
                continue
            if node1 is None or node2 is None:
                return False
            if node1.val != node2.val:
                return False
            stack.append((node1.right, node2.right))
            stack.append((node1.left, node2.left))
        return True

If you have any Other approach to this problem please do comment that down and if you find it useful please considering like and follow.