100. Same Tree

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Problem Description

The problem presents us with two binary trees and asks us to determine if they are the same. To be considered the same, every corresponding node in the two trees must have the same value and the same structure. This means that not only should the values of the nodes at the same positions match, but the shape of the trees must be identical as well. There should be no node in one tree that does not have a corresponding node in the same position of the other tree. This comparison should be consistent all the way down to the leaves of both trees.

Flowchart Walkthrough

Let's break down the problem using the Flowchart to determine the appropriate algorithm for solving LeetCode 100. Same Tree. Here's an analysis:

Is it a graph?

Yes: Although it's not explicitly presented as a typical graph, a tree structure can be considered a special type of graph.

Is it a tree?

Yes: The problem explicitly deals with comparing two binary trees, confirming that it involves tree data structures.

From the flowchart, when the structure is identified as a tree, the next step leads directly to using DFS (Depth-First Search).

Conclusion: According to the flowchart, the use of DFS is suggested for traversing and comparing the tree's nodes, ensuring that structures and values are identical in both trees.

Intuition

The intuition behind the solution to this problem involves recursion and understanding the nature of binary trees. Given two binary trees, the simplest case to compare them is when both trees are empty; they are obviously the same. The next step is to check the root nodes of both trees. If one is empty and the other is not, or if they have different values, then the trees are not the same.

However, if the root nodes match in value (and neither is None), we must then continue the comparison with their children. To do this, we apply the same comparison process to the left child of both trees and the right child of both trees.

This process is a typical example of a Depth-First Search (DFS) because it explores as far as possible along each branch before backtracking. In the provided solution, recursive function calls are made to compare the left children of p and q, and the right children of p and q, ensuring that each subtree is identical in both structure and value. This recursion continues until all nodes have been visited, or a mismatch is found.

This approach works efficiently since it has the ability to terminate early as soon as a mismatch is detected, without needing to check the rest of the tree.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution to this problem uses a recursive Depth-First Search (DFS) pattern to explore both trees simultaneously. The DFS algorithm repeatedly explores a branch as deeply as possible before backtracking. This approach is implemented by recursively checking each node pair of both trees.

Let's walk through the implementation in the provided code:

The base case checks if p and q are both None. If both are None, it means we've reached the end of both branches, the trees are identical so far, and we return True.
The next base case checks if one of the trees is None and the other is not, or if the current nodes' values do not match (p.val != q.val). Since the trees need to be structurally identical and have the same values, in these cases we return False.
If none of the base cases terminate the function, the code proceeds to check both the left and right subtrees by calling isSameTree recursively for p.left and q.left, and then for p.right and q.right.
The return value is the result of joining these two boolean checks with an and operator. The and operator ensures that both subtrees (left and right) need to be identical for the function to return True.

This recursion will "unravel" when it reaches the bottom of the trees (the leaves), at each stage combining the results from left and right comparisons until it reaches the initial call at the root. If all nodes are matched perfectly throughout the recursion, then the final result would be True, meaning both binary trees are the same.

The DFS pattern requires no additional data structures as it operates directly on the tree nodes and utilizes the system's call stack for its recursion.

Overall, the algorithm runs in O(n) time complexity where n is the number of nodes in the trees, as every node is visited once. The space complexity can be up to O(n) as well, particularly in the case of a completely unbalanced tree where a call stack proportionate to the number of nodes would be needed.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider two small binary trees A and B as an example to illustrate the solution approach.

Tree A:

  1
 / \
2   3

Tree B:

  1
 / \
2   3

Both trees appear to be structurally identical and also have the same node values corresponding to each position, but we need to use our algorithm to confirm this.

We start our recursive function isSameTree and check the root nodes of both trees A and B. The roots of both trees have the value 1. Since neither is None and both values match, we proceed with the recursive checks on the children.

Next, we compare the left children of the two trees (A.left and B.left) which are 2 and 2. We call isSameTree(A.left, B.left):

Since both values match and there are no more children to these nodes, the recursive call for these left children will eventually return True.

Next, we move on to compare the right children of the two trees (A.right and B.right) which are 3 and 3. We call isSameTree(A.right, B.right):

Again, since both values match and there are no further children, the recursive call for these right children will also return True.

Since both recursive calls resulted in True, we continue by combining these two results with an and operator:

isSameTree(A.left, B.left) and isSameTree(A.right, B.right) which is True and True, resulting in True.

Finally, as we have no more nodes left to compare and all matched perfectly, the unraveled recursive calls return back to the initial call invoking the root nodes, confirming that Tree A and Tree B are indeed the same. The isSameTree function would, therefore, return True for these two trees.

Solution Implementation

1class TreeNode:
2    # TreeNode class definition
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val    # value of the node
5        self.left = left  # left child
6        self.right = right  # right child
7
8class Solution:
9    def isSameTree(self, tree1: Optional[TreeNode], tree2: Optional[TreeNode]) -> bool:
10        """
11        Checks if two binary trees are the same.
12      
13        Args:
14        tree1 (Optional[TreeNode]): The root node of the first binary tree.
15        tree2 (Optional[TreeNode]): The root node of the second binary tree.
16      
17        Returns:
18        bool: True if both trees are identical, False otherwise.
19        """
20      
21        # If both trees are None, they are the same (both empty)
22        if tree1 == tree2:
23            return True
24      
25        # If one of the trees is None or the values of current nodes are different,
26        # then the trees are not the same.
27        if tree1 is None or tree2 is None or tree1.val != tree2.val:
28            return False
29      
30        # Otherwise, check recursively for the left and right subtrees.
31        # Both subtrees must be the same for the entire trees to be considered the same.
32        return self.isSameTree(tree1.left, tree2.left) and \
33               self.isSameTree(tree1.right, tree2.right)
34

1// Definition for a binary tree node.
2class TreeNode {
3    int val;        // value of the node
4    TreeNode left;  // left child
5    TreeNode right; // right child
6
7    // Constructor to create a new node with no children
8    TreeNode() {}
9
10    // Constructor to create a new node with a specified value
11    TreeNode(int val) {
12        this.val = val;
13    }
14
15    // Constructor to create a new node with a specified value and specified left and right children
16    TreeNode(int val, TreeNode left, TreeNode right) {
17        this.val = val;
18        this.left = left;
19        this.right = right;
20    }
21}
22
23class Solution {
24    public boolean isSameTree(TreeNode p, TreeNode q) {
25        // If both trees are empty, they are the same.
26        if (p == null && q == null) return true;
27
28        // If one of the trees is empty or the values of current nodes don't match,
29        // the trees aren't the same.
30        if (p == null || q == null || p.val != q.val) return false;
31
32        // Recursively check if the left subtree of both trees are the same 
33        // AND the right subtree of both trees are the same.
34        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
35    }
36}
37

1// Definition for a binary tree node.
2struct TreeNode {
3    int val;          // Value of the node
4    TreeNode *left;   // Pointer to the left child node
5    TreeNode *right;  // Pointer to the right child node
6    // Constructor to initialize the node with a value. By default, left and right pointers are null.
7    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8    // Constructor to create a node with a value, left child, and right child.
9    TreeNode(int x, TreeNode *leftChild, TreeNode *rightChild) : val(x), left(leftChild), right(rightChild) {}
10};
11
12class Solution {
13public:
14    // Function to check if two binary trees are the same.
15    bool isSameTree(TreeNode* p, TreeNode* q) {
16        // If both nodes are the same instance or both are null, trees are the same.
17        if (p == q) return true;
18        // If one of the nodes is null or the values don't match, trees are not the same.
19        if (!p || !q || p->val != q->val) return false;
20      
21        // Check recursively if left subtrees are the same and right subtrees are the same.
22        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
23    }
24};
25

1// Definition for a binary tree node.
2interface TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6}
7
8/**
9 * Determines if two binary trees are the same.
10 * Two binary trees are considered the same if they are structurally identical,
11 * and the nodes have the same values.
12 * 
13 * @param {TreeNode | null} tree1 - The root node of the first binary tree.
14 * @param {TreeNode | null} tree2 - The root node of the second binary tree.
15 * @return {boolean} - True if both trees are the same, false otherwise.
16 */
17function isSameTree(tree1: TreeNode | null, tree2: TreeNode | null): boolean {
18    // Check if both nodes are null, which implies that we've reached the end of both trees.
19    if (tree1 === null && tree2 === null) {
20        return true;
21    }
22    // If one of the nodes is null or if the values of the nodes do not match, the trees aren't the same.
23    if (tree1 === null || tree2 === null || tree1.val !== tree2.val) {
24        return false;
25    }
26  
27    // Recursively check the left and right subtrees.
28    return isSameTree(tree1.left, tree2.left) && isSameTree(tree1.right, tree2.right);
29}
30

Time and Space Complexity

The time complexity of the given isSameTree function is O(N) where N is the number of nodes in the smaller of the two trees being compared. This occurs because the function is called recursively on each node of the trees until it either finds a discrepancy or checks all pairs of corresponding nodes.

The space complexity is O(log(N)) in the best case (balanced trees) due to the recursive stack, which would reach at most the depth of the tree. In the worst case (completely unbalanced trees), the space complexity would be O(N) since the recursive calls would occur in a linear fashion, leading to a call stack size equal to the number of nodes in the tree.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know