NUHMAN.com

Introduction

LeetCode 100: Same Tree is a problem where you are asked to determine if two binary trees are identical. The two trees are considered identical if they are structurally identical and the nodes have the same values.

In this problem, you will implement an algorithm that compares two binary trees to check if they are the same.

Problem Statement

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if:

• They are structurally identical.
• The nodes have the same value.

Example:

go

Input: 
    Tree 1:
        [1, 2, 3]
    Tree 2:
        [1, 2, 3]
Output: true
Explanation: Both trees are identical.

Input: 
    Tree 1:
        [1, 2]
    Tree 2:
        [1, null, 2]
Output: false
Explanation: The structures of the trees are different.

Input: 
    Tree 1:
        [1, 2, 1]
    Tree 2:
        [1, 1, 2]
Output: false
Explanation: The trees have the same structure, but the values of the nodes are different.

Approach:

Recursive Approach

To determine if two trees are the same, we can recursively check the following:

1. Both trees must be non-null. If one is null and the other is not, they are not the same.
2. The root values of the trees must be equal.
3. The left subtrees of both trees must be the same.
4. The right subtrees of both trees must be the same.

The problem boils down to comparing the current node values and recursively checking the left and right subtrees. If any of these conditions fail, the trees are not identical.

Steps:

1. Base Case: If both trees are null, they are identical (return true). If one tree is null and the other is not, return false.
2. Compare Values: If the values of the current nodes in both trees are not equal, return false.
3. Recursion: Recursively check the left and right subtrees.

Go Implementation

Recursive Solution

go

package main

// TreeNode represents the structure of a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// isSameTree checks if two binary trees are the same.
func isSameTree(p *TreeNode, q *TreeNode) bool {
    // If both nodes are nil, trees are the same.
    if p == nil && q == nil {
        return true
    }
    
    // If one node is nil and the other is not, trees are different.
    if p == nil || q == nil {
        return false
    }
    
    // If the values of the nodes are not equal, trees are different.
    if p.Val != q.Val {
        return false
    }
    
    // Recursively check left and right subtrees.
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

Explanation:

1. TreeNode Structure:

• The TreeNode structure represents a binary tree node with three fields: Val (the value of the node), Left (pointer to the left child), and Right (pointer to the right child).

1. isSameTree Function:

• This function takes two TreeNode pointers p and q as input and returns a bool indicating whether the two binary trees rooted at p and q are the same.

1. Base Case:

• If both p and q are nil, return true (both trees are empty).
• If one is nil and the other is not, return false (the trees are not the same).
• If the values of p and q are not equal, return false.

1. Recursion:

• Recursively check if the left subtrees of p and q are the same and if the right subtrees of p and q are the same. Both conditions must hold true for the trees to be identical.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(h)

Where:

• n is the number of nodes in the binary tree.
• h is the height of the binary tree.

Time Complexity:

• We visit each node exactly once, so the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity:

• The space complexity depends on the recursion stack due to the recursive calls. In the worst case (a skewed tree), the space complexity is O(n), but for a balanced tree, the space complexity is O(h), where h is the height of the tree.

Edge Cases

1. Both Trees are Empty:

• Input: p = nil, q = nil
• Output: true
• Explanation: Two empty trees are considered the same.

1. One Tree is Empty, and the Other is Not:

• Input: p = [1], q = nil
• Output: false
• Explanation: One tree is empty, and the other is not, so they are not the same.

1. Identical Trees:

• Input: p = [1, 2, 3], q = [1, 2, 3]
• Output: true
• Explanation: Both trees have the same structure and values.

1. Different Structures:

• Input: p = [1, 2], q = [1, null, 2]
• Output: false
• Explanation: The structure of the two trees is different, so they are not the same.

1. Same Structure, Different Values:

• Input: p = [1, 2, 3], q = [1, 3, 2]
• Output: false
• Explanation: The structure is the same, but the node values are different, so they are not the same.

Conclusion

LeetCode 100: Same Tree is a simple but important problem that checks if two binary trees are identical. The recursive approach with direct comparisons of node values and recursive checks of subtrees is efficient and easy to implement. The solution has a time complexity of O(n) and a space complexity of O(h), where n is the number of nodes and h is the height of the tree. This approach is optimal for comparing binary trees in most scenarios.