Last updated on January 19th, 2025 at 05:56 pm
Here, we see a Same Tree LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Depth-First Search, Tree
Companies
Bloomberg
Level of Question
Easy

Same Tree LeetCode Solution
Table of Contents
1. Problem Statement
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
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is Tree Traversal. Specifically:
- The C++ code uses an Iterative Breadth-First Search (BFS) approach with a queue.
- The Java and Python code use a Recursive Depth-First Search (DFS) approach.
- The JavaScript code uses a Serialization and Comparison approach by converting the trees into JSON strings and comparing them.
3. Code Implementation in Different Languages
3.1 Same Tree C++
class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { queue<TreeNode *> queue; queue.push(p); queue.push(q); while (queue.size()!=0){ TreeNode * q2=queue.front(); queue.pop(); TreeNode * q1=queue.front(); queue.pop(); if (q1==nullptr && q2==nullptr) continue; if (q1==nullptr || q2==nullptr) return false; if (q1->val!=q2->val) return false; queue.push(q1->left); queue.push(q2->left); queue.push(q1->right); queue.push(q2->right); } return true; } };
3.2 Same Tree Java
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; return p != null && q != null && p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } }
3.3 Same Tree JavaScript
var isSameTree = function(p, q) { return JSON.stringify(p)===JSON.stringify(q) };
3.4 Same Tree Python
class Solution(object): def isSameTree(self, p, q): if p==None and q==None: return True elif p==None or q==None: return False if p.val==q.val: return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) else: return False
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n) | O(n) |
Java | O(n) | O(h) |
JavaScript | O(n) | O(n) |
Python | O(n) | O(h) |
where h is the height of the tree.