🔄 PHP Tree Traversal

DFS — Inorder (Left → Root → Right)

Inorder on a BST gives sorted order.

function inorder(?TreeNode $root): array {
    if ($root === null) return [];
    return [...inorder($root->left), $root->val, ...inorder($root->right)];
}
// [4, 2, 5, 1, 3]

Iterative inorder:

function inorderIterative(?TreeNode $root): array {
    $result = [];
    $stack  = [];
    $curr   = $root;
    while ($curr !== null || !empty($stack)) {
        while ($curr !== null) {
            $stack[] = $curr;
            $curr    = $curr->left;
        }
        $curr     = array_pop($stack);
        $result[] = $curr->val;
        $curr     = $curr->right;
    }
    return $result;
}

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

---

DFS — Preorder (Root → Left → Right)

Good for copying/serializing a tree.

function preorder(?TreeNode $root): array {
    if ($root === null) return [];
    return [$root->val, ...preorder($root->left), ...preorder($root->right)];
}
// [1, 2, 4, 5, 3]

---

DFS — Postorder (Left → Right → Root)

Good for deleting a tree or computing subtree results bottom-up.

function postorder(?TreeNode $root): array {
    if ($root === null) return [];
    return [...postorder($root->left), ...postorder($root->right), $root->val];
}
// [4, 5, 2, 3, 1]

---

BFS — Level-Order Traversal

function levelOrder(?TreeNode $root): array {
    if ($root === null) return [];
    $result = [];
    $queue  = [$root];
    while (!empty($queue)) {
        $level = [];
        $size  = count($queue);
        for ($i = 0; $i < $size; $i++) {
            $node    = array_shift($queue);
            $level[] = $node->val;
            if ($node->left  !== null) $queue[] = $node->left;
            if ($node->right !== null) $queue[] = $node->right;
        }
        $result[] = $level;
    }
    return $result;
    // [[1], [2, 3], [4, 5]]
}

Time: O(n) | Space: O(w) where w = max width

---

Zigzag Level-Order

Alternate left-to-right and right-to-left per level.

function zigzagLevelOrder(?TreeNode $root): array {
    if ($root === null) return [];
    $result    = [];
    $queue     = [$root];
    $leftToRight = true;
    while (!empty($queue)) {
        $size  = count($queue);
        $level = [];
        for ($i = 0; $i < $size; $i++) {
            $node    = array_shift($queue);
            $level[] = $node->val;
            if ($node->left)  $queue[] = $node->left;
            if ($node->right) $queue[] = $node->right;
        }
        $result[] = $leftToRight ? $level : array_reverse($level);
        $leftToRight = !$leftToRight;
    }
    return $result;
}

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

---

Right Side View

Return the rightmost node at each level.

function rightSideView(?TreeNode $root): array {
    if ($root === null) return [];
    $result = [];
    $queue  = [$root];
    while (!empty($queue)) {
        $size = count($queue);
        for ($i = 0; $i < $size; $i++) {
            $node = array_shift($queue);
            if ($i === $size - 1) $result[] = $node->val;
            if ($node->left)  $queue[] = $node->left;
            if ($node->right) $queue[] = $node->right;
        }
    }
    return $result;
}

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

---

Pattern Summary