Problem: You have been given roots of two binary trees p and q. Check whether the two binary tress are same or not. If two Binary trees are same return true else return false.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Example 1:
Input: p = [1, 2, 3], q = [1, 2, 3]
Output: true
Output: true
Example 2:
Input: p = [1, 2, 3], q = [1, 2, 3, 4]
Output: false
Output: false
Approach:
The approach we are using is recursive approach. We will check if p and q values are same or not. Then, we will perform the same check on subtree until we get the result.
Code Implementation:
public class isSameTree {
static class Node {
int data;
Node left, right;
Node(int key) {
data = key;
left = right = null;
}
}
public static void main(String[] ans) {
// Tree 1
Node p = new Node(1);
p.left = new Node(2);
p.right = new Node(3);
// Tree 2
Node q = new Node(1);
q.left = new Node(2);
q.right = new Node(3);
// passing roots to below method
System.out.println(isSame(p, q));
}
private static boolean isSame(Node p, Node q) {
// p and q both are null
if (p == null && q == null)
return true;
// either one of them is null
if (p == null || q == null)
return false;
/*
* check p.val == q.val and call isSameTree for p.left, q.left and call
* isSameTree for p.right, q.right
*/
return (p.data == q.data) && isSame(p.left, q.left) && isSame(p.right, q.right);
}
}
Output:
true
Complexity Analysis:
Time Complexity: O(n), where n is the number of nodes in tree.
Space Complexity: Considering the stack space, if the tree is balanced then O(log n) and if tree is unbalanced then O(n).