# Same Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/same-tree)
Canonical: https://scaleengineer.com/dsa/problems/same-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Merkle Tree](https://scaleengineer.com/algorithms/merkle-tree)
**Data structures:** Tree, Binary Tree
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Flipkart](https://scaleengineer.com/companies/flipkart), [Google](https://scaleengineer.com/companies/google), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Yahoo](https://scaleengineer.com/companies/yahoo), [tcs](https://scaleengineer.com/companies/tcs)
---
## 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:**

![](https://assets.glich.co/dsa/same-tree/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/same-tree/image1.jpg) 

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

**Example 3:**

![](https://assets.glich.co/dsa/same-tree/image2.jpg) 

**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`

# Approaches
## Tree Serialization and Comparison
This approach involves converting each tree into a unique string representation (a process called serialization). If the resulting strings for both trees are identical, the trees are considered the same. A pre-order traversal is a good candidate for serialization, ensuring that `null` children are also represented to capture the tree's structure accurately.
**Time:** O(N + M), where N and M are the number of nodes in the trees. We must traverse every node in both trees to build the strings, and the final string comparison takes O(N + M) time in the worst case. · **Space:** O(N + M), where N and M are the number of nodes in trees p and q, respectively. This space is used to store the string representations. The recursion stack for serialization also contributes O(H) space, where H is the tree height.
**Pros:** It's a conceptually straightforward approach if you are familiar with tree serialization.; It leverages a standard technique that can be reused for other problems like serializing/deserializing a tree.
**Cons:** This approach is inefficient because it cannot short-circuit. It traverses both entire trees even if a difference is found at the root.; It uses significant extra space to build the full string representations of both trees.; The overhead of string building and comparison can be substantial compared to direct node-by-node comparison.
### Explanation
The core idea is to transform the 2D tree structure into a 1D string format. We can define a recursive function that performs a pre-order traversal on a tree. When it encounters a node, it appends the node's value to a string. When it encounters a `null` child, it appends a special marker (like '#') to signify the absence of a node. This is crucial to distinguish between trees like `[1,2]` and `[1,null,2]`. After generating the serialized strings for both trees `p` and `q`, we simply compare them. If the strings are equal, the trees are structurally and valuably identical.

```java
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        StringBuilder sb1 = new StringBuilder();
        serialize(p, sb1);
        String s1 = sb1.toString();

        StringBuilder sb2 = new StringBuilder();
        serialize(q, sb2);
        String s2 = sb2.toString();

        return s1.equals(s2);
    }

    private void serialize(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#,");
            return;
        }
        sb.append(node.val).append(",");
        serialize(node.left, sb);
        serialize(node.right, sb);
    }
}
```
### Algorithm
*   Define a helper function `serialize(node, stringBuilder)` that performs a pre-order traversal.
*   In the helper function, if the current `node` is `null`, append a special marker (e.g., "#") and a delimiter to the string builder.
*   If the `node` is not `null`, append its value and a delimiter, then recursively call `serialize` for the left and right children.
*   Create two `StringBuilder` instances.
*   Call the `serialize` function for the root of tree `p` and tree `q` to generate their string representations.
*   Compare the two resulting strings. If they are equal, the trees are identical.

## Iterative Traversal with a Queue (BFS)
A more efficient approach is to traverse both trees simultaneously. This can be done iteratively using a queue, which corresponds to a Breadth-First Search (BFS). We add pairs of corresponding nodes from each tree to the queue and compare them one by one. This ensures we check the trees level by level and can stop as soon as we find any discrepancy.
**Time:** O(N), where N is the number of nodes in the smaller tree. We visit each node at most once. The traversal stops as soon as a mismatch is found. · **Space:** O(W), where W is the maximum width of the trees. In the worst case of a complete binary tree, the last level can contain up to N/2 nodes, leading to O(N) space.
**Pros:** Efficient in both time and space.; Avoids recursion, thus preventing any risk of stack overflow on extremely deep trees.; Stops the comparison immediately upon finding the first difference, making it fast for non-identical trees.
**Cons:** The code is slightly more complex and less intuitive to write compared to the recursive version.; For balanced trees, the queue can grow up to O(N) in size, potentially using more memory than the recursive approach's O(log N) stack space.
### Explanation
This method avoids recursion by managing the nodes to visit with an explicit queue. We start by adding the roots of both trees to the queue. Then, we enter a loop that continues as long as there are nodes to check. In each step, we dequeue a pair of nodes. We first check for structural differences or value mismatches. If any are found, we immediately know the trees are not the same and return `false`. If the current pair of nodes are valid and identical, we enqueue their children to be checked in subsequent iterations. This process continues until the queue is empty, which means all corresponding nodes have been checked and found to be identical.

```java
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        // Initial check for root nodes
        if (p == null && q == null) return true;
        if (p == null || q == null || p.val != q.val) return false;
        
        queue.offer(p);
        queue.offer(q);

        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();

            // Compare left children
            TreeNode left1 = node1.left;
            TreeNode left2 = node2.left;
            if (left1 == null && left2 == null) {
                // Both null, do nothing
            } else if (left1 == null || left2 == null || left1.val != left2.val) {
                return false;
            } else {
                queue.offer(left1);
                queue.offer(left2);
            }

            // Compare right children
            TreeNode right1 = node1.right;
            TreeNode right2 = node2.right;
            if (right1 == null && right2 == null) {
                // Both null, do nothing
            } else if (right1 == null || right2 == null || right1.val != right2.val) {
                return false;
            } else {
                queue.offer(right1);
                queue.offer(right2);
            }
        }
        return true;
    }
}
```
### Algorithm
*   Initialize a queue (e.g., `LinkedList`) and add both root nodes, `p` and `q`, to it.
*   Loop while the queue is not empty.
*   In each iteration, poll two nodes from the queue, `node1` from `p`'s lineage and `node2` from `q`'s.
*   If both `node1` and `node2` are `null`, they match, so `continue` to the next pair.
*   If one of the nodes is `null` but the other isn't, or if their values are not equal, the trees are different. Return `false`.
*   If the nodes match, add their children to the queue in a specific order: first the left children (`node1.left`, `node2.left`), then the right children (`node1.right`, `node2.right`).
*   If the loop completes without returning `false`, it means all nodes matched. Return `true`.

## Recursive Traversal (DFS)
The most elegant and intuitive solution is recursive. The problem's definition—two trees are the same if their roots match and their left and right subtrees are also the same—maps directly to a recursive function. This approach is clean, concise, and effectively performs a depth-first search on both trees simultaneously.
**Time:** O(N), where N is the number of nodes in the smaller tree, as we have to visit each node at most once. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst case of a completely skewed tree, the height is N, leading to O(N) space. For a balanced tree, the height is log(N), leading to O(log N) space.
**Pros:** The code is extremely simple, concise, and easy to understand.; It directly mirrors the logical definition of what makes two trees the same.; It is highly efficient, stopping as soon as a difference is found.
**Cons:** For extremely deep trees, this approach could lead to a stack overflow error due to deep recursion. However, this is not a concern with the problem's constraint of at most 100 nodes.; Recursive function calls can have slightly more overhead than a purely iterative loop.
### Explanation
This approach breaks the problem down into smaller, identical subproblems. The function `isSameTree(p, q)` checks three conditions:
1.  Are both nodes `null`? If so, they are the same.
2.  Is one `null` and the other not, or do their values differ? If so, they are not the same.
3.  If the current nodes are the same, are their subtrees also the same? This is checked by making two recursive calls: one for the left subtrees (`p.left`, `q.left`) and one for the right subtrees (`p.right`, `q.right`).
The trees are only considered identical if the current nodes match AND both the left and right subtree comparisons return `true`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 1. Both are null, they are the same.
        if (p == null && q == null) {
            return true;
        }
        // 2. One is null, but not both, or values differ. They are not the same.
        if (p == null || q == null || p.val != q.val) {
            return false;
        }
        // 3. Recursively check left and right subtrees.
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
```
### Algorithm
*   Check the base cases first:
    *   If both nodes `p` and `q` are `null`, they are identical at this branch. Return `true`.
    *   If only one of `p` or `q` is `null`, or if their values (`p.val`, `q.val`) are different, they are not identical. Return `false`.
*   If the base cases are passed, the current nodes are identical. Now, check their subtrees.
*   Recursively call the function for the left children: `isSameTree(p.left, q.left)`.
*   Recursively call the function for the right children: `isSameTree(p.right, q.right)`.
*   Return `true` only if both recursive calls return `true`, otherwise return `false`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Same_Tree { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution_iteration { public boolean isSameTree ( TreeNode p , TreeNode q ) { if ( p == null ) { return q == null ; } if ( q == null ) { return p == null ; } Stack < TreeNode > sk1 = new Stack < TreeNode >(); Stack < TreeNode > sk2 = new Stack < TreeNode >(); sk1 . push ( p ); sk2 . push ( q ); while (! sk1 . isEmpty () && ! sk2 . isEmpty ()) { TreeNode current1 = sk1 . pop (); TreeNode current2 = sk2 . pop (); if ( current1 == null && current2 == null ) { continue ; // @note: missed both null check } else if ( current1 == null && current2 != null ) { return false ; } else if ( current1 != null && current2 == null ) { return false ; } else if ( current1 . val != current2 . val ) { return false ; } sk1 . push ( current1 . left ); sk2 . push ( current2 . left ); sk1 . push ( current1 . right ); sk2 . push ( current2 . right ); } // final check if (! sk1 . isEmpty () || ! sk2 . isEmpty ()) { return false ; } return true ; } } public class Solution_recursion { public boolean isSameTree ( TreeNode p , TreeNode q ) { if ( p == null ) { return q == null ; } if ( q == null ) { return p == null ; } if ( p . val != q . val ) { return false ; } return isSameTree ( p . left , q . left ) && isSameTree ( p . right , q . right ); } } } ////// class Solution { public boolean isSameTree ( TreeNode p , TreeNode q ) { if ( p == q ) return true ; if ( p == null || q == null || p . val != q . val ) return false ; return isSameTree ( p . left , q . left ) && isSameTree ( p . right , q . right ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} p * @param {TreeNode} q * @return {boolean} */ var isSameTree =
  function (p, q) {
    if (!p && !q) return true;
    if (p && q) {
      return (
        p.val === q.val &&
        isSameTree(p.left, q.left) &&
        isSameTree(p.right, q.right)
      );
    }
    return false;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isSameTree ( TreeNode * p , TreeNode * q ) { if ( p == q ) return true ; if ( ! p || ! q || p -> val != q -> val ) return false ; return isSameTree ( p -> left , q -> left ) && isSameTree ( p -> right , q -> right ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution ( object ): def isSameTree ( self , p , q ): """ :type p: TreeNode :type q: TreeNode :rtype: bool """ if not p or not q : return p == q # covers: p=none and q!=none, q=none and p!=none, both none return p . val == q . val and self . isSameTree ( p . left , q . left ) and self . isSameTree ( p . right , q . right ) # iteration class Solution : def isSameTree ( self , p : TreeNode , q : TreeNode ) -> bool : if p is None : return q is None if q is None : return p is None stack1 = [ p ] stack2 = [ q ] while stack1 and stack2 : current1 = stack1 . pop () current2 = stack2 . pop () if current1 is None and current2 is None : continue elif current1 is None or current2 is None : return False elif current1 . val != current2 . val : return False stack1 . append ( current1 . left ) stack2 . append ( current2 . left ) stack1 . append ( current1 . right ) stack2 . append ( current2 . right ) return not stack1 and not stack2
```