100: Same Tree#
Difficulty: Easy
Link to Problem: To see the Same Tree problem on LeetCode, click here!
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.
Constraints
The number of nodes in both trees is in the range
[0, 100]
.\(-10^4\) <= Node.val <= \(10^4\)
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
# Initialize a TreeNode with a value (val), left child, and right child.
self.val = val
self.left = left
self.right = right
def isSameTree(p, q):
# Base case: If both p and q are None, the trees are the same.
if not p and not q:
return True
# Base case: If either p or q is None (but not both), the trees are different.
if not p or not q:
return False
# Check if the values of the current nodes (p.val and q.val) are equal.
if p.val != q.val:
return False
# Recursively check the left and right subtrees of p and q.
# If both subtrees are the same, the entire trees are the same.
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
In this code, we define a TreeNode
class to represent binary tree nodes and a isSameTree
function to check if two binary trees are the same. The function uses recursive traversal to compare the trees’ structures and values.
We start by defining a
TreeNode
class, which represents a node in a binary tree. Each node has aval
(the node’s value), aleft
child, and a right child. This class will help us create and work with binary trees.Next, we define the
isSameTree
function, which checks if two binary trees (p
andq
) are the same.The base case for the recursion is when both
p
andq
areNone
. In this case, they are considered the same, so we returnTrue
.If either
p
orq
isNone
(but not both), they cannot be the same, so we returnFalse
.If the values of the current nodes
p.val
andq.val
are not equal, we returnFalse
because the trees cannot be the same.Finally, we recursively check the left and right subtrees of
p
andq
to see if they are the same.
Test cases#
### Example 1
#Input: `p = [1,2,3]`, `q = [1,2,3]`
p1 = TreeNode(1, TreeNode(2), TreeNode(3))
q1 = TreeNode(1, TreeNode(2), TreeNode(3))
print(isSameTree(p1, q1))
True
### Example 2
#Input: `p = [1,2]`, `q = [1,null,2]`
p2 = TreeNode(1, TreeNode(2), None)
q2 = TreeNode(1, None, TreeNode(2))
print(isSameTree(p2, q2))
False
### Example 3
#Input: p = [1,2,1], q = [1,1,2]
p3 = TreeNode(1, TreeNode(2), TreeNode(1))
q3 = TreeNode(1, TreeNode(1), TreeNode(2))
print(isSameTree(p3, q3))
False
Time Complexity#
The time complexity of the isSameTree
function can be analyzed as follows:
In the worst case, the function needs to visit every node in both trees once to determine if they are the same. Since each node is visited exactly once, the time complexity is \(O(n)\), where \(n\) is the total number of nodes in the input trees.
Space Complexity#
The space complexity of the isSameTree
function can be analyzed as follows:
The space used by the function’s call stack during recursion is proportional to the maximum depth of the binary trees. In the worst case, when the trees are completely unbalanced (all nodes form a single branch), the maximum depth will be \(n\), where \(n\) is the total number of nodes in the input trees. Therefore, the space complexity is \(O(n)\) due to the recursive call stack. In addition to the call stack, there is a small constant amount of space used for variables and comparisons within each recursive call, but this space is not significant in terms of the overall space complexity.
In summary:#
Time Complexity: \(O(n)\) where \(n\) is the total number of nodes in the input trees.
Space Complexity: \(O(n)\) due to the recursive call stack.