Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0100 - Same Tree
    0100 - Same Tree
    0100 - Same Tree
    0100 - Same Tree

    0100 - Same Tree

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/same-tree/

    Solution 1 - Recursive DFS

    Given the roots of two binary trees p and q, check if they are structurally identical and all corresponding nodes have the same value. We use a recursive depth-first search: if both nodes are None, they match; if only one is None or values differ, they don't match; otherwise, recursively check both left and right subtrees.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    Solution 2 - Iterative BFS using Queue

    Instead of recursion, use a queue to compare nodes level by level. Push pairs of nodes from both trees and compare them iteratively. This avoids potential stack overflow for very deep trees.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 0100.1 - Same Tree - Solution 1 - Recursive DFS """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        """Same Tree Function"""
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: p = [1,2,3], q = [1,2,3] -> True
    p1 = TreeNode(1, TreeNode(2), TreeNode(3))
    q1 = TreeNode(1, TreeNode(2), TreeNode(3))
    print(Solution().isSameTree(p1, q1))

    # Example 2: p = [1,2], q = [1,null,2] -> False
    p2 = TreeNode(1, TreeNode(2))
    q2 = TreeNode(1, None, TreeNode(2))
    print(Solution().isSameTree(p2, q2))

    # Example 3: p = [1,2,1], q = [1,1,2] -> False
    p3 = TreeNode(1, TreeNode(2), TreeNode(1))
    q3 = TreeNode(1, TreeNode(1), TreeNode(2))
    print(Solution().isSameTree(p3, q3))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0100.2 - Same Tree - Solution 2 - Iterative BFS using Queue """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional
from collections import deque

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        """Same Tree Function"""
        queue = deque([(p, q)])

        while queue:
            node_p, node_q = queue.popleft()

            if not node_p and not node_q:
                continue
            if not node_p or not node_q:
                return False
            if node_p.val != node_q.val:
                return False

            queue.append((node_p.left, node_q.left))
            queue.append((node_p.right, node_q.right))

        return True


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: p = [1,2,3], q = [1,2,3] -> True
    p1 = TreeNode(1, TreeNode(2), TreeNode(3))
    q1 = TreeNode(1, TreeNode(2), TreeNode(3))
    print(Solution().isSameTree(p1, q1))

    # Example 2: p = [1,2], q = [1,null,2] -> False
    p2 = TreeNode(1, TreeNode(2))
    q2 = TreeNode(1, None, TreeNode(2))
    print(Solution().isSameTree(p2, q2))

    # Example 3: p = [1,2,1], q = [1,1,2] -> False
    p3 = TreeNode(1, TreeNode(2), TreeNode(1))
    q3 = TreeNode(1, TreeNode(1), TreeNode(2))
    print(Solution().isSameTree(p3, q3))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()