Comparing Binary Trees for Equality in PHP: An Elegant Approach

Binary trees are fundamental data structures in computer science, often used to represent hierarchical relationships between elements. Determining whether two binary trees are identical, i.e., they have the same structure and same node values, is an important task in various applications. In this Medium post, we’ll explore a PHP solution that elegantly compares two binary trees for equality.

Introduction

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

Exploring the Code

Let’s delve into the PHP class Solution and its method isSameTree($p, $q):

class Solution {

    /**
     * @param TreeNode $p
     * @param TreeNode $q
     * @return Boolean
     */
    function isSameTree($p, $q) {
      if ($p === null && $q === null) return true;
      if ($p === null || $q === null || $p->val != $q->val) return false;

      return ($this->isSameTree($p->left, $q->left) &&
             $this->isSameTree($p->right, $q->right));
    }
}

How It Works

1. Base Cases:
   - If both trees are empty (i.e., both p and q are null), they are identical, so the function returns true.
   - If one of the trees is empty while the other is not, or if the values of the corresponding nodes are different, the trees are not identical, and the function returns false.
2. Recursive Comparison:
   - If the base cases are not met, the function recursively compares the left and right subtrees of both trees.
   - If all corresponding nodes have the same values and their subtrees are identical, the function returns true. Otherwise, it returns false.

Time and Space Complexity

Time Complexity:

• In the worst-case scenario, where both trees are completely unbalanced and have n nodes each, the time complexity is O(n). This is because the function traverses each node of both trees once.

Space Complexity:

• The space complexity is O(h), where ℎ is the height of the binary trees. This is because the recursive calls consume space on the call stack, and the maximum depth of the call stack is determined by the height of the trees.
• In the worst-case scenario, where the trees are completely unbalanced and have n nodes each, the height ℎ can be O(n). However, in balanced trees, the height is typically O(logn).

Conclusion

The provided PHP solution elegantly compares two binary trees for equality using a recursive approach.

Happy Coding :)