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:

p = 
   1      
  / \    
 2   3  

q = 
   1      
  / \    
 2   3 

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

Java
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);
}
Rust
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,
        }
    }
}

A regular rust user would see this line

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

and deduce that Eq is already derived for TreeNode and hence the equivalence of TreeNode can just as simple as p == q

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

Go
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
}
Java
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();
}
Rust
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

Java
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();
}