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.

For e.g. in the below diagram, example 1 has identical trees but example 2 doesnt.

Examples

Example 1

flowchart LR
    subgraph p ["Tree p"]
        A(1):::orange
        B(2):::orange
        C(3):::orange
        A --- B & C
    end
    subgraph q ["Tree q"]
        D(1):::green
        E(2):::green
        F(3):::green
        D --- E & F
    end
    p <==>|Identical| q

    classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff; 
classDef blue fill:#0000FF,stroke:#000,stroke-width:1px,color:#fff;
classDef orange fill:#DC582A,stroke:#333,stroke-width:2px;

linkStyle 4 stroke:blue,stroke-width:2px
  
1
2

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

Example 2

flowchart LR
    subgraph p ["Tree p"]
        A(1)
        B(2)
        A --- B
        A ~~~ N1:::hidden
    end
    subgraph q ["Tree q"]
        D(1)
        E(2)
        D ~~~ N2:::hidden
        D --- E
    end
    
    
    p <==>|Not Identical| q
    classDef hidden display:none
  
1
2

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3

flowchart LR
    subgraph p ["Tree p"]
        A(1)
        B(2)
        C(1)
        A --- B
        A --- C
    end
    subgraph q ["Tree q"]
        D(1)
        E(1)
        F(2)
        D --- E
        D --- F
    end
    p <==>|Not Identical| q
  
1
2

Input: p = [1,2,1], q = [1,1,2]
Output: false

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).

Video explanation

Here is the video explaining this method in detail. Please check it out:

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