Binary trees and BSTs — traversal, search

Advanced5 min read·eng-07-004

compare

Concept

Binary Tree: Each node has at most two children — left and right. No ordering constraint. Parent-child structure for hierarchical data.

Binary Search Tree (BST): A binary tree with the BST property: left subtree < node < right subtree for every node. This property enables O(log n) search, insert, and delete on a BALANCED BST.

Balanced vs unbalanced: A balanced BST has height O(log n). An unbalanced BST (e.g., inserting sorted data into a naive BST) degrades to a linked list: height O(n), all operations O(n).

Self-balancing BSTs (not in PHP SPL): AVL tree, Red-Black tree. These maintain balance automatically.

BST operations:

search(value): O(log n) balanced, O(n) worst case.
insert(value): O(log n) average.
delete(value): O(log n) average.
min() / max(): O(log n) — leftmost / rightmost node.

Tree traversals (all O(n) — visit every node):

In-order (left → root → right): Visits BST nodes in sorted order.
Pre-order (root → left → right): Used to copy/serialize a tree.
Post-order (left → right → root): Used to delete a tree (process children before parent).
Level-order (BFS): Visit level by level. Uses a queue.

PHP use cases: Implementing autocomplete (Trie), expression parsing, database index internals (B-trees are a generalization), sorted data structures.

SPL doesn't have a BST. Use sorted arrays with usort() for most PHP work. Implement BST when the problem requires it.

Code Example

php

<?php
class TreeNode
{
    public function __construct(
        public int       $value,
        public ?TreeNode $left  = null,
        public ?TreeNode $right = null,
    ) {}
}

class BinarySearchTree
{
    private ?TreeNode $root = null;

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

    private function insertNode(?TreeNode $node, int $value): TreeNode
    {
        if ($node === null) return new TreeNode($value);
        if ($value < $node->value)      $node->left  = $this->insertNode($node->left, $value);
        elseif ($value > $node->value)  $node->right = $this->insertNode($node->right, $value);
        // equal → ignore (no duplicates in standard BST)
        return $node;
    }

    public function search(int $value): bool
    {
        $current = $this->root;
        while ($current !== null) {
            if ($value === $current->value) return true;
            $current = $value < $current->value ? $current->left : $current->right;
        }
        return false;
    }

    // Traversals
    public function inOrder(): array   { $r = []; $this->inOrderTraverse($this->root, $r); return $r; }
    public function preOrder(): array  { $r = []; $this->preOrderTraverse($this->root, $r); return $r; }
    public function levelOrder(): array
    {
        if ($this->root === null) return [];
        $queue = new \SplQueue();
        $queue->enqueue($this->root);
        $result = [];
        while (!$queue->isEmpty()) {
            $node     = $queue->dequeue();
            $result[] = $node->value;
            if ($node->left)  $queue->enqueue($node->left);
            if ($node->right) $queue->enqueue($node->right);
        }
        return $result;
    }

    private function inOrderTraverse(?TreeNode $node, array &$result): void
    {
        if ($node === null) return;
        $this->inOrderTraverse($node->left, $result);
        $result[] = $node->value;                       // root BETWEEN subtrees
        $this->inOrderTraverse($node->right, $result);
    }

    private function preOrderTraverse(?TreeNode $node, array &$result): void
    {
        if ($node === null) return;
        $result[] = $node->value;                       // root FIRST
        $this->preOrderTraverse($node->left, $result);
        $this->preOrderTraverse($node->right, $result);
    }

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

$bst = new BinarySearchTree();
foreach ([5, 3, 7, 1, 4, 6, 8] as $v) { $bst->insert($v); }

print_r($bst->inOrder());    // [1, 3, 4, 5, 6, 7, 8] — sorted!
print_r($bst->levelOrder()); // [5, 3, 7, 1, 4, 6, 8] — breadth-first
echo $bst->search(4);        // true
echo $bst->search(9);        // false

PreviousStacks and queues — SplStack, SplQueue, array implementationsData Structures in PHP NextHeaps and priority queues — SplMinHeap, SplMaxHeapData Structures in PHP