Same Tree

EASY

Description

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].
-10⁴ <= Node.val <= 10⁴

Approaches

Checkout 3 different approaches to solve Same Tree. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Same Tree. Click on different languages to view the code.

/** * 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 ); } }

Video Solution

Watch the video walkthrough for Same Tree

Algorithms:

Depth-First SearchBreadth-First Search

Data Structures:

TreeBinary Tree

Companies:

Adobe |Amazon |Apple |Bloomberg |