## Monday, May 16, 2022

### Easy_Question8 : Same Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

#### Approach 1: Recursion.

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// p and q are both null
if (p == null && q == null) return true;
// one of p and q is null
if (q == null || p == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.right, q.right) &&
isSameTree(p.left, q.left);
}
}

#### Approach 2: Iteration

class Solution {
public boolean check(TreeNode p, TreeNode q) {
// p and q are null
if (p == null && q == null) return true;
// one of p and q is null
if (q == null || p == null) return false;
if (p.val != q.val) return false;
return true;
}

public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (!check(p, q)) return false;

// init deques
ArrayDeque<TreeNode> deqP = new ArrayDeque<TreeNode>();
ArrayDeque<TreeNode> deqQ = new ArrayDeque<TreeNode>();

while (!deqP.isEmpty()) {
p = deqP.removeFirst();
q = deqQ.removeFirst();

if (!check(p, q)) return false;
if (p != null) {
// in Java nulls are not allowed in Deque
if (!check(p.left, q.left)) return false;
if (p.left != null) {
}
if (!check(p.right, q.right)) return false;
if (p.right != null) {
}
}
}
return true;
}
}



Complexity Analysis

• Time complexity : $\mathcal{O}(N)$ since each node is visited exactly once.

• Space complexity : $\mathcal{O}(\log(N))$ in the best case of completely balanced tree and $\mathcal{O}(N)$ in the worst case of completely unbalanced tree, to keep a deque.

## You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS