🌳 PHP Tree Basics

Node Structure

class TreeNode {
    public int $val;
    public ?TreeNode $left;
    public ?TreeNode $right;

    public function __construct(int $val = 0, ?TreeNode $left = null, ?TreeNode $right = null) {
        $this->val   = $val;
        $this->left  = $left;
        $this->right = $right;
    }
}

---

Building a Binary Tree Manually

$root       = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right= new TreeNode(3);
$root->left->left  = new TreeNode(4);
$root->left->right = new TreeNode(5);

//       1
//      / \
//     2   3
//    / \
//   4   5

---

Key Terminology

---

Binary Search Tree (BST)

A BST satisfies: left < root < right at every node.

class BST {
    public ?TreeNode $root = null;

    public function insert(int $val): void {
        $this->root = $this->insertNode($this->root, $val);
    }

    private function insertNode(?TreeNode $node, int $val): TreeNode {
        if ($node === null) return new TreeNode($val);
        if ($val < $node->val)      $node->left  = $this->insertNode($node->left,  $val);
        else if ($val > $node->val) $node->right = $this->insertNode($node->right, $val);
        return $node;
    }

    public function search(int $val): bool {
        return $this->searchNode($this->root, $val);
    }

    private function searchNode(?TreeNode $node, int $val): bool {
        if ($node === null)     return false;
        if ($val === $node->val) return true;
        return $val < $node->val
            ? $this->searchNode($node->left,  $val)
            : $this->searchNode($node->right, $val);
    }
}

$bst = new BST();
$bst->insert(5); $bst->insert(3); $bst->insert(7);
$bst->insert(1); $bst->insert(4);
var_dump($bst->search(4)); // true
var_dump($bst->search(6)); // false

Time: O(log n) average, O(n) worst (skewed) | Space: O(h) recursion stack

---

Tree Height

function height(?TreeNode $node): int {
    if ($node === null) return 0;
    return 1 + max(height($node->left), height($node->right));
}

Time: O(n) | Space: O(h)

---

Count Nodes

function countNodes(?TreeNode $node): int {
    if ($node === null) return 0;
    return 1 + countNodes($node->left) + countNodes($node->right);
}

---

Check if Balanced

A balanced tree: |height(left) − height(right)| ≤ 1 at every node.

function isBalanced(?TreeNode $root): bool {
    return checkHeight($root) !== -1;
}

function checkHeight(?TreeNode $node): int {
    if ($node === null) return 0;
    $l = checkHeight($node->left);
    if ($l === -1) return -1;
    $r = checkHeight($node->right);
    if ($r === -1) return -1;
    if (abs($l - $r) > 1) return -1;
    return 1 + max($l, $r);
}

Time: O(n) | Space: O(h)

---

Complexity Summary