Same Tree solution and explanation
Google
TCS
9 more videos on this problem
Same Tree - Leetcode 100 - PythonNeetCode · 7:52 · 189K views
Same Tree (LeetCode 100) | Full solution with visuals and animations | Study AlgorithmsNikhil Lohia · 14:16 · 14K views
Same Binary Tree - Leetcode 100 - Trees (Python)Greg Hogg · 5:55 · 12K views
Same Tree | LeetCode 100 | Google Coding Interview TutorialTerrible Whiteboard · 9:25 · 3K views
100. Same Tree Leetcode Problem | Solution with Explanation | DSA Problem SeriesCoding Blocks · 4:15 · 1K views
Same Tree Leetcode Javascript | 100 Same Tree LeetcodePersistent Programmer · 10:36 · 1K views
LeetCode 100: The Same Tree - Interview Prep Ep 21Fisher Coder · 10:47 · 1K views
Same Tree - LeetCode 100 - Python #blind75 #leetcodeDeepti Talesra · 10:27 · 1K views
100. Same Tree | JavaScript | Depth First Search | LeetCode Daily Challenge | Simple ExplanationLeetCodeWithMonu · 5:25 · 996 views
How To Solve "100 Same Tree" on LeetCode - JavaScript EasyBecoming A Better Dev (with David) · 6:14 · 957 views
The 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 1:
Input: p = [1,2,3], q = [1,2,3] Output: true
Example 2:
Input: p = [1,2], q = [1,null,2] Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2] Output: false
Constraints:
- The number of nodes in both trees is in the range
[0, 100]. -104 <= Node.val <= 104
Approach overview
Problem Overview: You receive two binary trees and need to determine whether they are exactly the same. Two trees are considered the same if they have identical structure and every corresponding node contains the same value.
The comparison must check both structure and values simultaneously. If any node differs in value, or if one tree has a node where the other has null, the trees are not the same.
Approach 1: Recursive Comparison (DFS) (Time: O(n), Space: O(h))
This approach performs a depth-first traversal of both trees at the same time. Start from the root nodes and compare them. If both nodes are null, that subtree matches. If only one node is null or their values differ, the trees are different. Otherwise recursively compare the left children and then the right children.
The key insight: identical trees must match node-by-node and subtree-by-subtree. Recursion naturally mirrors the structure of a binary tree, making the logic straightforward. Each node is visited once, giving O(n) time complexity where n is the number of nodes. The recursion stack depth equals the tree height, which is O(h) space.
This method is the most common solution in interviews and production code because it is concise and clearly expresses the structure comparison.
Approach 2: Iterative Approach using Stacks (Time: O(n), Space: O(h))
The iterative version replaces recursion with an explicit stack. Push a pair of nodes from both trees onto the stack. Repeatedly pop a pair and compare them. If both are null, continue. If one is null or their values differ, return false. Otherwise push their left children as a pair and their right children as another pair.
This method performs the same traversal pattern as a Depth-First Search. The stack holds pairs of nodes that still need comparison. Like the recursive solution, every node is processed once, giving O(n) time. The stack grows at most to the height of the tree, so space complexity is O(h).
An iterative solution is useful when recursion depth could cause stack overflow or when you want explicit control over traversal order. The logic also mirrors how DFS works internally.
Recommended for interviews: The recursive DFS comparison is usually the expected answer because it directly models the problem and takes only a few lines of code. Interviewers often accept the iterative stack solution as well, especially if you explain how it simulates recursion. Understanding both approaches demonstrates solid knowledge of tree traversal and DFS patterns.
Approach 1: Recursive Comparison
This approach involves recursively checking each node of the trees. You start at the roots and compare their values. If they are the same, you proceed to check their left and right subtrees. If at any point the checks fail (either structure or node values don't match), you conclude that the trees are not identical.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
return (p.val == q.val) and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
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);
}
}#include <iostream>
using namespace std;
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
if (!p || !q) return false;
return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}function TreeNode(val, left = null, right = null) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var isSameTree = function(p, q) {
if (!p && !q) return true;
if (!p || !q) return false;
return (p.val === q.val) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};#include <stdbool.h>
typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
if (!p || !q) return false;
return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public bool 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);
}
}The Python version of the solution defines a TreeNode class and implements the isSameTree function to recursively compare the trees starting from the root node, evaluating each node's value and subtree structure.
The time complexity is O(N), where N is the number of nodes, because all nodes are checked once. It also has O(H) space complexity due to recursion where H is the height of the tree.
Approach 2: Iterative Approach using Stacks
This approach involves using a stack to iteratively check whether two trees are identical. You use a stack to simulate the recursive process, always working on node pairs from both trees. For every processed pair, check for value equality, then push their children into the stack to process afterwards (with left and right children being compared correspondingly).
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isSameTree(p, q):
stackP = [p]
stackQ = [q]
while stackP and stackQ:
nodeP = stackP.pop()
nodeQ = stackQ.pop()
if not nodeP and not nodeQ:
continue
if not nodeP or not nodeQ or nodeP.val != nodeQ.val:
return False
stackP.append(nodeP.right)
stackP.append(nodeP.left)
stackQ.append(nodeQ.right)
stackQ.append(nodeQ.left)
return not stackP and not stackQimport java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
Stack<TreeNode> stackP = new Stack<>();
Stack<TreeNode> stackQ = new Stack<>();
stackP.push(p);
stackQ.push(q);
while (!stackP.isEmpty() && !stackQ.isEmpty()) {
TreeNode nodeP = stackP.pop();
TreeNode nodeQ = stackQ.pop();
if (nodeP == null && nodeQ == null) continue;
if (nodeP == null || nodeQ == null || nodeP.val != nodeQ.val) return false;
stackP.push(nodeP.right);
stackP.push(nodeP.left);
stackQ.push(nodeQ.right);
stackQ.push(nodeQ.left);
}
return stackP.isEmpty() && stackQ.isEmpty();
}
}#include <stack>
using namespace std;
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
bool isSameTree(TreeNode* p, TreeNode* q) {
stack<TreeNode*> stackP, stackQ;
stackP.push(p);
stackQ.push(q);
while (!stackP.empty() && !stackQ.empty()) {
TreeNode* nodeP = stackP.top(); stackP.pop();
TreeNode* nodeQ = stackQ.top(); stackQ.pop();
if (!nodeP && !nodeQ) continue;
if (!nodeP || !nodeQ || nodeP->val != nodeQ->val) return false;
stackP.push(nodeP->right); stackP.push(nodeP->left);
stackQ.push(nodeQ->right); stackQ.push(nodeQ->left);
}
return stackP.empty() && stackQ.empty();
}function TreeNode(val, left = null, right = null) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var isSameTree = function(p, q) {
let stackP = [p], stackQ = [q];
while (stackP.length && stackQ.length) {
let nodeP = stackP.pop();
let nodeQ = stackQ.pop();
if (!nodeP && !nodeQ) continue;
if (!nodeP || !nodeQ || nodeP.val !== nodeQ.val) return false;
stackP.push(nodeP.right);
stackP.push(nodeP.left);
stackQ.push(nodeQ.right);
stackQ.push(nodeQ.left);
}
return stackP.length === 0 && stackQ.length === 0;
};#include <stdbool.h>
#include <stdlib.h>
#include "stack.h"
typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;
bool isSameTree(TreeNode* p, TreeNode* q) {
Stack *stackP = createStack();
Stack *stackQ = createStack();
push(stackP, p);
push(stackQ, q);
while (!isEmpty(stackP) && !isEmpty(stackQ)) {
TreeNode* nodeP = pop(stackP);
TreeNode* nodeQ = pop(stackQ);
if (!nodeP && !nodeQ) continue;
if (!nodeP || !nodeQ || nodeP->val != nodeQ->val) return false;
push(stackP, nodeP->left);
push(stackP, nodeP->right);
push(stackQ, nodeQ->left);
push(stackQ, nodeQ->right);
}
return isEmpty(stackP) && isEmpty(stackQ);
}using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public bool IsSameTree(TreeNode p, TreeNode q) {
Stack<TreeNode> stackP = new Stack<TreeNode>();
Stack<TreeNode> stackQ = new Stack<TreeNode>();
stackP.Push(p);
stackQ.Push(q);
while (stackP.Count > 0 && stackQ.Count > 0) {
TreeNode nodeP = stackP.Pop();
TreeNode nodeQ = stackQ.Pop();
if (nodeP == null && nodeQ == null)
continue;
if (nodeP == null || nodeQ == null || nodeP.val != nodeQ.val)
return false;
stackP.Push(nodeP.right);
stackP.Push(nodeP.left);
stackQ.Push(nodeQ.right);
stackQ.Push(nodeQ.left);
}
return stackP.Count == 0 && stackQ.Count == 0;
}
}This Python implementation uses lists as stacks to iteratively compare tree nodes. Both lists maintain pairs of nodes being checked for structure and value equality at this iteration.
Time complexity is O(N), where all nodes are processed once. Space is O(H), depending on the maximum depth of nodes pushed on stacks.
Approach 3: DFS
We can use the DFS recursive method to solve this problem.
First, determine whether the root nodes of the two binary trees are the same. If both root nodes are null, then the two binary trees are the same. If only one of the root nodes is null, then the two binary trees are definitely different. If both root nodes are not null, then determine whether their values are the same. If they are not the same, then the two binary trees are definitely different. If they are the same, then determine whether the left subtrees of the two binary trees are the same and whether the right subtrees are the same. The two binary trees are the same only when all the above conditions are met.
The time complexity is O(min(m, n)), and the space complexity is O(min(m, n)). Here, m and n are the number of nodes in the two binary trees, respectively. The space complexity mainly depends on the number of layers of recursive calls, which will not exceed the number of nodes in the smaller binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (p == null && q == null) {
return true;
}
if (p == null || q == null || p.val !== q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == q {
return true
}
if p == nil || q == nil || p.Val != q.Val {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
fn dfs(p: &Option<Rc<RefCell<TreeNode>>>, q: &Option<Rc<RefCell<TreeNode>>>) -> bool {
if p.is_none() && q.is_none() {
return true;
}
if p.is_none() || q.is_none() {
return false;
}
let r1 = p.as_ref().unwrap().borrow();
let r2 = q.as_ref().unwrap().borrow();
r1.val == r2.val && Self::dfs(&r1.left, &r2.left) && Self::dfs(&r1.right, &r2.right)
}
pub fn is_same_tree(
p: Option<Rc<RefCell<TreeNode>>>,
q: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
Self::dfs(&p, &q)
}
}/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($val = 0, $left = null, $right = null) {
* $this->val = $val;
* $this->left = $left;
* $this->right = $right;
* }
* }
*/
class Solution {
/**
* @param TreeNode $p
* @param TreeNode $q
* @return Boolean
*/
function isSameTree($p, $q) {
if ($p == null && $q == null) {
return true;
}
if ($p == null || $q == null) {
return false;
}
if ($p->val != $q->val) {
return false;
}
return $this->isSameTree($p->left, $q->left) && $this->isSameTree($p->right, $q->right);
}
}Approach 4: BFS
We can also use the BFS iterative method to solve this problem.
First, add the root nodes of the two binary trees to two queues. Each time, take out one node from each of the two queues and perform the following comparison operations. If the values of the two nodes are not the same, then the structures of the two binary trees are definitely different. If the values of the two nodes are the same, then determine whether the child nodes of the two nodes are null. If only the left child node of one node is null, then the structures of the two binary trees are definitely different. If only the right child node of one node is null, then the structures of the two binary trees are definitely different. If the structures of the left and right child nodes are the same, then add the left and right child nodes of the two nodes to the two queues respectively. For the next iteration, take out one node from each of the two queues for comparison. When both queues are empty at the same time, it means that we have compared all the nodes, and the structures of the two binary trees are completely the same.
The time complexity is O(min(m, n)), and the space complexity is O(min(m, n)). Here, m and n are the number of nodes in the two binary trees, respectively. The space complexity mainly depends on the number of elements in the queue, which will not exceed the number of nodes in the smaller binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
const queue = [];
p && queue.push(p);
q && queue.push(q);
if (queue.length === 1) {
return false;
}
while (queue.length !== 0) {
const node1 = queue.shift();
const node2 = queue.shift();
if (node1.val !== node2.val) {
return false;
}
if (
(node1.left == null && node2.left != null) ||
(node1.left != null && node2.left == null)
) {
return false;
}
if (
(node1.right == null && node2.right != null) ||
(node1.right != null && node2.right == null)
) {
return false;
}
if (node1.left != null) {
queue.push(node1.left);
queue.push(node2.left);
}
if (node1.right != null) {
queue.push(node1.right);
queue.push(node2.right);
}
}
return true;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == q {
return true
}
if p == nil || q == nil {
return false
}
q1 := []*TreeNode{p}
q2 := []*TreeNode{q}
for len(q1) > 0 && len(q2) > 0 {
p, q = q1[0], q2[0]
if p.Val != q.Val {
return false
}
q1, q2 = q1[1:], q2[1:]
la, ra := p.Left, p.Right
lb, rb := q.Left, q.Right
if (la != nil && lb == nil) || (lb != nil && la == nil) {
return false
}
if (ra != nil && rb == nil) || (rb != nil && ra == nil) {
return false
}
if la != nil {
q1 = append(q1, la)
q2 = append(q2, lb)
}
if ra != nil {
q1 = append(q1, ra)
q2 = append(q2, rb)
}
}
return true
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn is_same_tree(
mut p: Option<Rc<RefCell<TreeNode>>>,
mut q: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
let mut queue = VecDeque::new();
if p.is_some() {
queue.push_back(p.take());
}
if q.is_some() {
queue.push_back(q.take());
}
if queue.len() == 1 {
return false;
}
while queue.len() != 0 {
if let (Some(mut node1), Some(mut node2)) = (queue.pop_front(), queue.pop_front()) {
let mut node1 = node1.as_mut().unwrap().borrow_mut();
let mut node2 = node2.as_mut().unwrap().borrow_mut();
if node1.val != node2.val {
return false;
}
match (node1.left.is_some(), node2.left.is_some()) {
(false, false) => {}
(true, true) => {
queue.push_back(node1.left.take());
queue.push_back(node2.left.take());
}
(_, _) => {
return false;
}
}
match (node1.right.is_some(), node2.right.is_some()) {
(false, false) => {}
(true, true) => {
queue.push_back(node1.right.take());
queue.push_back(node2.right.take());
}
(_, _) => {
return false;
}
}
}
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Comparison | The time complexity is O(N), where N is the number of nodes, because all nodes are checked once. It also has O(H) space complexity due to recursion where H is the height of the tree. |
| Iterative Approach using Stacks | Time complexity is O(N), where all nodes are processed once. Space is O(H), depending on the maximum depth of nodes pushed on stacks. |
| DFS | – |
| BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Comparison (DFS) | O(n) | O(h) | Most common solution. Clean and concise when recursion depth is safe. |
| Iterative DFS using Stack | O(n) | O(h) | Useful when avoiding recursion or when explicit stack control is preferred. |
Frequently asked questions
Is Same Tree easy or hard?
Same Tree is categorized as an Easy problem. It focuses on basic binary tree traversal and recursion patterns, making it a common introductory question for tree-based algorithms.
How to solve Same Tree in O(n)?
Traverse both trees simultaneously using DFS. At each step compare the current nodes: if both are null continue, if only one is null or their values differ return false. Recursively or iteratively compare left children and right children. Each node is processed once, resulting in O(n) time.
What is the best approach for Same Tree?
The recursive depth-first comparison is the most common and clean solution. You compare the current nodes of both trees, then recursively compare their left and right children. Each node is visited once, giving O(n) time and O(h) recursion stack space where h is the tree height.
Is Same Tree asked at Google/Amazon/Meta?
Same Tree is a common binary tree interview problem and appears frequently across companies such as Amazon, Meta, and Google in different variations. It tests understanding of tree traversal, recursion, and structural comparison.
What data structure is used in Same Tree?
The problem operates on a binary tree data structure. Solutions typically use Depth-First Search traversal, either through recursion or an explicit stack to compare nodes from both trees.
What is the time complexity of Same Tree?
The time complexity is O(n) because each node in the trees is visited once during comparison. In the worst case both trees contain n nodes and every corresponding pair must be checked.
Same Tree Python or Java solution approach?
Both Python and Java implementations typically use a recursive DFS function that compares node values and recursively checks left and right children. The logic is identical across languages and runs in O(n) time with O(h) stack space.