Problem

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.

Example

Input: Two binary Search Trees

Check if Two Binary Tree’s are Identical

Example 1:

1
2
3
4
5
6
7
8
9

p = 
   1      
  / \    
 2   3  

q = 
   1      
  / \    
 2   3 

1
2

Input: p = [1,2,3], q = [1,2,3]
Output: true

Solution

Method 1 - Recursive

Algorithm

  • Recursive Traversal: Begin by traversing both trees simultaneously from their roots.
  • Match Check: If either root is null or their data doesn’t match, return false (structural or value mismatch).
  • Subtree Verification: Recursively check if p.left is a subtree of q.left and p.right is a subtree of q.right.
  • Completion Consistency: If one tree finishes traversing (null) while the other has nodes, return false (structural difference).
  • Match Confirmation: If both trees reach the end simultaneously (both null), return true (trees match).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

    return p.val == q.val &&
        isSameTree(p.left, q.left) &&
        isSameTree(p.right, q.right);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn is_same_tree(p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> bool {
        match (p, q) {
            (None, None) => true,
            (Some(p), Some(q)) => {
                let p = p.borrow();
                let q = q.borrow();
                p.val == q.val
                    && Self::is_same_tree(p.left.clone(), q.left.clone())
                    && Self::is_same_tree(p.right.clone(), q.right.clone())
            }
            _ => false,
        }
    }
}
 
1
2

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
 
1
2
3

pub fn is_same_tree(p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> bool {
    p == q
}

Method 2 - Iterative using Level Order Traversal

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func isSameTree(p *TreeNode, q *TreeNode) bool {
    type Pair struct {
        p, q *TreeNode
    }
    var queue []Pair
    queue = append(traverse, Pair{p, q})
    for len(traverse) > 0 {
        pair := queue[len(traverse) - 1]
        traverse = queue[:len(traverse) - 1]
        if pair.p != nil && pair.q != nil && pair.p.Val == pair.q.Val {
            traverse = append(traverse, Pair{pair.p.Left, pair.q.Left})
            traverse = append(traverse, Pair{pair.p.Right, pair.q.Right})
        } else if pair.p != nil || pair.q != nil {
            return false
        }
    }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public boolean isSameTree(TreeNode p, TreeNode q) {
	Queue<TreeNode> queue1 = new LinkedList<>();
	Queue<TreeNode> queue2 = new LinkedList<>();

	queue1.offer(p);
	queue2.offer(q);

	while (!queue1.isEmpty() && !queue2.isEmpty()) {
		TreeNode node1 = queue1.poll();
		TreeNode node2 = queue2.poll();

		if (node1 == null && node2 == null) {
			continue;
		}
		if (node1 == null || node2 == null || node1.val != node2.val) {
			return false;
		}

		queue1.offer(node1.left);
		queue1.offer(node1.right);
		queue2.offer(node2.left);
		queue2.offer(node2.right);
	}

	return queue1.isEmpty() && queue2.isEmpty();
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn is_same_tree(p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> bool {
        let mut queue = Vec::new();
        queue.push((p, q));
        while let Some((mut p, mut q)) = queue.pop() {
            if p.is_none() != q.is_none() {
                return false
            } else if let (Some(p), Some(q)) = (p.take(), q.take()) {
                let (mut p, mut q) = (p.borrow_mut(), q.borrow_mut());
                if p.val != q.val {
                    return false
                }
                queue.push((p.left.take(), q.left.take()));
                queue.push((p.right.take(), q.right.take()));
            }
        }
        true
    }
}

Method 3 - Iterative using DFS

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public boolean isSameTree(TreeNode p, TreeNode q) {
	Stack<TreeNode> stack1 = new Stack<>();
	Stack<TreeNode> stack2 = new Stack<>();

	stack1.push(p);
	stack2.push(q);

	while (!stack1.isEmpty() && !stack2.isEmpty()) {
		TreeNode node1 = stack1.pop();
		TreeNode node2 = stack2.pop();

		if (node1 == null && node2 == null) {
			continue;
		} else if (node1 == null || node2 == null || node1.val != node2.val) {
			return false;
		}

		stack1.push(node1.left);
		stack2.push(node2.left);

		stack1.push(node1.right);
		stack2.push(node2.right);
	}

	return stack1.isEmpty() && stack2.isEmpty();
}