Leetcode: Same Tree

Difficulty: Easy

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

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Runtime Analysis:

No boundary conditions are given. Solution written is O(n) because we call isSameTree() recursively on every node in the tree. Memory is also O(h) where h is the height of the tree. This is due to the top down nature of recursive calls. One call will keep going until it hits the base case, then bubble up level by level. The max call stack that we will need to maintain is therefore, O(h).

Runtime: O(n)
Space: O(h)

Algorithmic Approach:

This question requires a basic understanding of Binary Trees. Every Node in a Binary Tree at most 2 children (a left and right child). In order to check if 2 Binary Trees are identical, we need to check for:

1. Structural Identity
2. Value Identity

We have 3 basic cases:
1. p and q are both null, our trees are identical if both roots are null

2. p or q is null, our trees are not identical because one root is not null

3. p and q are different values, our trees are not identical because the value for the roots are not the same

4. If conditions (1), (2), and (3)  are not met, then we recursively compare the left and right subtrees of p and q

Java Code:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        
        if(p == null && q == null)
            return true;

        if(p == null || q == null)
            return false;

        if(p.val != q.val)
            return false;
        
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); 

    }
}