Same Binary Tree
Same Binary Tree – Easy Level Problem
Given the roots of two binary trees, p and q, return true if the trees are identical; otherwise, return false.
Two binary trees are considered identical if they have the same structure and their corresponding nodes contain the same values.
Example 1:
Illustration 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Output: true
Example 2:
Illustration 2:
Input: p = [4,7], q = [4,null,7]
Output: false
Output: false
Constraints:
- 0 <= The number of nodes in both trees <= 100.
- -100 <= Node.val <= 100
Hints to Solve Same Binary Tree
Recommendation for Time and Space Complexity:
Aim for a solution with a time complexity of O(n) and a space complexity of O(n), where n is the total number of nodes in the tree.
Hints For Solving Same Binary Tree Problem
Hint 1 :
Can you think of a tree traversal algorithm that works using recursion?
Hint 2 :
Depth First Search (DFS) is a good choice for tree traversal. How can we use it to traverse both trees simultaneously?
Hint 3 :
Start by comparing the root nodes of both trees. At each recursive step, check if both nodes are null or have the same value. If one node is null and the other isn’t, or if their values don’t match, return false. If they match, recursively compare their left and right sub trees. If any recursive call returns false, the trees are not identical.
There are mainly 2 approach to solve this problem:
- Depth First Search Method (DFS)
- Breadth First Search Method (BFS)
1. Depth First Search (DFS) Method
Use recursion or a stack to traverse both trees simultaneously, comparing nodes one by one. Check left and right sub trees at each step, ensuring both structure and values match.
- Time complexity: O(n)
- Space complexity: O(h)
- Best Case (balanced tree): O(log(n))
- Worst Case (degenerate tree): O(n)
Where,
- n is the number of nodes in the tree.
- h is the height of the tree.
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) {
return true;
}
if (p && q && p->val == q->val) {
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
} else {
return false;
}
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p != null && q != null && p.val == q.val) {
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
} else {
return false;
}
}
}
Python
# 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: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if p and q and p.val == q.val:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
else:
return False
JavaScript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
isSameTree(p, q) {
if (!p && !q) {
return true;
}
if (p && q && p.val === q.val) {
return (
this.isSameTree(p.left, q.left) &&
this.isSameTree(p.right, q.right)
);
} else {
return false;
}
}
}
2. Breadth First Search (BFS) Method
Use a queue to traverse both trees level by level, comparing corresponding nodes. Ensure both trees have the same structure and values as you process each level.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
queue q1;
queue q2;
q1.push(p);
q2.push(q);
while (!q1.empty() && !q2.empty()) {
TreeNode* nodeP = q1.front(); q1.pop();
TreeNode* nodeQ = q2.front(); q2.pop();
if (!nodeP && !nodeQ) continue;
if (!nodeP || !nodeQ || nodeP->val != nodeQ->val)
return false;
q1.push(nodeP->left);
q1.push(nodeP->right);
q2.push(nodeQ->left);
q2.push(nodeQ->right);
}
return true;
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
Queue q1 = new LinkedList<>();
Queue q2 = new LinkedList<>();
q1.add(p);
q2.add(q);
while (!q1.isEmpty() && !q2.isEmpty()) {
TreeNode nodeP = q1.poll();
TreeNode nodeQ = q2.poll();
if (nodeP == null && nodeQ == null) continue;
if (nodeP == null || nodeQ == null || nodeP.val != nodeQ.val)
return false;
q1.add(nodeP.left);
q1.add(nodeP.right);
q2.add(nodeQ.left);
q2.add(nodeQ.right);
}
return true;
}
}
Python
# 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: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
q1 = deque([p])
q2 = deque([q])
while q1 and q2:
nodeP = q1.popleft()
nodeQ = q2.popleft()
if nodeP is None and nodeQ is None:
continue
if nodeP is None or nodeQ is None or nodeP.val != nodeQ.val:
return False
q1.append(nodeP.left)
q1.append(nodeP.right)
q2.append(nodeQ.left)
q2.append(nodeQ.right)
return True
JavaScript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
isSameTree(p, q) {
const q1 = new Queue();
const q2 = new Queue();
q1.push(p);
q2.push(q);
while (!q1.isEmpty() && !q2.isEmpty()) {
let nodeP = q1.pop();
let nodeQ = q2.pop();
if (nodeP === null && nodeQ === null) continue;
if (nodeP === null || nodeQ === null || nodeP.val !== nodeQ.val)
return false;
q1.push(nodeP.left);
q1.push(nodeP.right);
q2.push(nodeQ.left);
q2.push(nodeQ.right);
}
return true;
}
}
3. Breadth First Search Method
The BFS method uses a queue to traverse the tree level by level. Nodes at the same depth are processed together. By counting the levels traversed, you determine the maximum depth of the tree. This approach is efficient for level-order traversal.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
queue<TreeNode*> q;
if (root != nullptr) {
q.push(root);
}
int level = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) { TreeNode* node = q.front(); q.pop(); if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
level++;
}
return level;
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public int maxDepth(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
if (root != null) {
q.add(root);
}
int level = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
if (node.left != null) {
q.add(node.left);
}
if (node.right != null) {
q.add(node.right);
}
}
level++;
}
return level;
}
}
Python
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
q = deque()
if root:
q.append(root)
level = 0
while q:
for i in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
level += 1
return level
JavaScript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {TreeNode} root
* @return {number}
*/
maxDepth(root) {
const q = new Queue();
if (root !== null) {
q.push(root);
}
let level = 0;
while (q.size() > 0) {
const size = q.size();
for (let i = 0; i < size; i++) {
const node = q.pop();
if (node.left !== null) {
q.push(node.left);
}
if (node.right !== null) {
q.push(node.right);
}
}
level++;
}
return level;
}
}
