Same Tree LeetCode Solution

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

Same Tree LeetCode Solution

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 ComplexitySpace Complexity
C++O(n)O(n)
JavaO(n)O(h)
JavaScriptO(n)O(n)
PythonO(n)O(h)

where h is the height of the tree.

Scroll to Top