Understanding Tree Inversion in Binary Trees: A PHP Implementation

Inverting a binary tree involves swapping the left and right children of each node, resulting in a mirror image of the original tree. In this Medium post, we’ll explore a PHP solution that efficiently inverts a binary tree.

Introduction

Given the root of a binary tree, invert the tree, and return its root.

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Exploring the Code

Let’s examine the PHP class Solution and its method invertTree($root):

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return TreeNode
     */
    function invertTree($root) {
        if ($root === null) {
            return $root;
        }
        $temp = $root->left;
        $root->left = $root->right;
        $root->right = $temp;

        $this->invertTree($root->left);
        $this->invertTree($root->right);
        return $root;
    }
}

How It Works

1. Base Case: The function checks if the current node $root is null. If it is, it returns null, indicating the end of the subtree.
2. Swapping Children:
   - If $root is not null, the function swaps its left and right children by storing the left child in a temporary variable $temp, then assigning the right child to the left and the temporary variable to the right.
3. Recursion: The function recursively calls itself for the left and right subtrees, effectively inverting them.
4. Return Value: Finally, the function returns the modified $root node

Time and space complexity

• Time Complexity: O(n), Each node is visited once due to recursion.
• Space Complexity:
  - h is the height of the tree.
  - worst case: O(n),space might be required due to the recursive call stack
  - for balanced trees: O(logn)

Conclusion

The provided PHP solution efficiently inverts a binary tree using a recursive approach.

Happy Coding :)