Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
1 | 1
/ \ | / \
2 3 | 2 3
The above trees are the same as the structure is identical and nodes have the same value.
1 | 1
/ \ | / \
2 1 | 1 2
The above trees are not the same because nodes don't have the same value.
If you're curious to solve this problem before checking out the solution. Try it out in Leetcode 😉 .
You can find my solutions to other leetcode problems at https://github.com/harsha-sam/Leetcode-Solutions.
Solution
I'll be using the boilerplate code from leetcode. You can directly submit the solution and verify, once you understand how the algorithm works.
- Depth-first search both trees at the same time and return false if the structure is not identical or if the node values don't match.
# 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:
return self.helper(p, q)
def helper(self, node1, node2):
# returns false if structure is not identical
if node1 and not node2 or node2 and not node1:
return False
elif node1 and node2:
if not self.helper(node1.left, node2.left):
return False
if node1.val != node2.val:
return False
if not self.helper(node1.right, node2.right):
return False
return True
Time Complexity: O(N)
Space Complexity: O(tree height)
Top comments (0)