Same Tree
EasyPrompt
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: trueExample 2:
Input: p = [1,2], q = [1,null,2]
Output: falseExample 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
Approaches
3 approaches with complexity analysis and trade-offs.
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
nodeisnull, append a special marker (e.g., "#") and a delimiter to the string builder. - If the
nodeis notnull, append its value and a delimiter, then recursively callserializefor the left and right children. - Create two
StringBuilderinstances. - Call the
serializefunction for the root of treepand treeqto generate their string representations. - Compare the two resulting strings. If they are equal, the trees are identical.
Walkthrough
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
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.
Trade-offs
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.
Solutions
Solution
/** * 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 walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.