🎯 PHP Trees — Top 25 Interview Questions

---

Q1 — Maximum Depth of Binary Tree

🧠 How to Approach This

Step 1 — Recognize the pattern: Height = 1 + max(left height, right height); base case null → 0.

Step 2 — Brute force (what NOT to do): BFS counting levels — works but more code.

Step 3 — Optimal insight: Single DFS recursion; return value bubbles up the max depth.

Step 4 — Algorithm:

1. If node null → return 0

2. Recurse left and right

3. Return 1 + max(left, right)

Step 5 — Edge cases: Empty tree → 0; single node → 1.

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

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

---

Q2 — Invert Binary Tree

🧠 How to Approach This

Step 1 — Recognize the pattern: Swap left/right children recursively at every node.

Step 2 — Brute force (what NOT to do): Rebuild the tree — wasteful.

Step 3 — Optimal insight: Swap children in-place then recurse.

Step 4 — Algorithm:

1. If null → return null

2. Swap left and right

3. Recurse on both children

Step 5 — Edge cases: Null root; single node.

function invertTree(?TreeNode $root): ?TreeNode {
    if ($root === null) return null;
    [$root->left, $root->right] = [$root->right, $root->left];
    invertTree($root->left);
    invertTree($root->right);
    return $root;
}

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

---

Q3 — Symmetric Tree

🧠 How to Approach This

Step 1 — Recognize the pattern: Mirror check — left.left mirrors right.right, left.right mirrors right.left.

Step 2 — Brute force (what NOT to do): Inorder traversal palindrome check — fails for some cases.

Step 3 — Optimal insight: Recursive helper comparing two subtrees as mirrors.

Step 4 — Algorithm:

1. isMirror(left, right): both null → true; one null → false

2. vals equal AND isMirror(l.left, r.right) AND isMirror(l.right, r.left)

Step 5 — Edge cases: Single node → true; root null → true.

function isSymmetric(?TreeNode $root): bool {
    return isMirror($root?->left, $root?->right);
}
function isMirror(?TreeNode $l, ?TreeNode $r): bool {
    if ($l === null && $r === null) return true;
    if ($l === null || $r === null) return false;
    return $l->val === $r->val
        && isMirror($l->left,  $r->right)
        && isMirror($l->right, $r->left);
}

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

---

Q4 — Path Sum

🧠 How to Approach This

Step 1 — Recognize the pattern: Subtract root value at each step; check leaf when remainder = 0.

Step 2 — Brute force (what NOT to do): Enumerate all root-to-leaf paths then sum — O(n log n) space.

Step 3 — Optimal insight: Pass remaining target down; at leaf check if exactly 0 remaining.

Step 4 — Algorithm:

1. If null → false

2. remaining = targetSum - root.val

3. If leaf and remaining == 0 → true

4. Return hasPathSum(left, rem) || hasPathSum(right, rem)

Step 5 — Edge cases: Empty tree; negative values allowed.

function hasPathSum(?TreeNode $root, int $targetSum): bool {
    if ($root === null) return false;
    $rem = $targetSum - $root->val;
    if ($root->left === null && $root->right === null) return $rem === 0;
    return hasPathSum($root->left, $rem) || hasPathSum($root->right, $rem);
}

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

---

Q5 — Level Order Traversal

🧠 How to Approach This

Step 1 — Recognize the pattern: BFS with level-size tracking.

Step 2 — Brute force (what NOT to do): DFS with level markers — more complex.

Step 3 — Optimal insight: Process queue in batches of current level size.

Step 4 — Algorithm:

1. Init queue with root

2. While queue not empty: capture size, process that many nodes, enqueue children

Step 5 — Edge cases: Empty tree → [].

function levelOrder(?TreeNode $root): array {
    if ($root === null) return [];
    $result = [];
    $queue  = [$root];
    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[] = $level;
    }
    return $result;
}

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

---

Q6 — Validate Binary Search Tree

🧠 How to Approach This

Step 1 — Recognize the pattern: Every node must be within (min, max) bounds passed down from ancestors.

Step 2 — Brute force (what NOT to do): Inorder check — misses some valid-looking but invalid trees.

Step 3 — Optimal insight: Pass min/max bounds; tighten at each step.

Step 4 — Algorithm:

1. validate(node, min=−∞, max=+∞)

2. If val ≤ min or val ≥ max → false

3. Recurse left with max=val, right with min=val

Step 5 — Edge cases: Duplicate values; INT_MIN/INT_MAX nodes.

function isValidBST(?TreeNode $root): bool {
    return validate($root, PHP_INT_MIN, PHP_INT_MAX);
}
function validate(?TreeNode $node, int $min, int $max): bool {
    if ($node === null) return true;
    if ($node->val <= $min || $node->val >= $max) return false;
    return validate($node->left,  $min,       $node->val)
        && validate($node->right, $node->val, $max);
}

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

---

Q7 — Lowest Common Ancestor of BST

🧠 How to Approach This

Step 1 — Recognize the pattern: In BST, if both p and q < root → LCA in left; both > root → right; else root is LCA.

Step 2 — Brute force (what NOT to do): General LCA without using BST property — O(n).

Step 3 — Optimal insight: BST property narrows direction without visiting all nodes.

Step 4 — Algorithm:

1. If p.val and q.val both < root.val → recurse left

2. If both > root.val → recurse right

3. Else → root is LCA

Step 5 — Edge cases: p or q equals root itself.

function lowestCommonAncestor(TreeNode $root, TreeNode $p, TreeNode $q): TreeNode {
    if ($p->val < $root->val && $q->val < $root->val)
        return lowestCommonAncestor($root->left,  $p, $q);
    if ($p->val > $root->val && $q->val > $root->val)
        return lowestCommonAncestor($root->right, $p, $q);
    return $root;
}

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

---

Q8 — Lowest Common Ancestor of Binary Tree

🧠 How to Approach This

Step 1 — Recognize the pattern: Post-order DFS — find p or q in subtrees; if both sides return non-null → current node is LCA.

Step 2 — Brute force (what NOT to do): Store root-to-node paths then find last common — O(n) space.

Step 3 — Optimal insight: Single DFS returning the node when found; LCA is where both sides return non-null.

Step 4 — Algorithm:

1. If null or matches p/q → return node

2. Recurse left and right

3. If both non-null → return root; else return whichever is non-null

Step 5 — Edge cases: p is ancestor of q.

function lcaBinaryTree(?TreeNode $root, TreeNode $p, TreeNode $q): ?TreeNode {
    if ($root === null || $root === $p || $root === $q) return $root;
    $left  = lcaBinaryTree($root->left,  $p, $q);
    $right = lcaBinaryTree($root->right, $p, $q);
    if ($left !== null && $right !== null) return $root;
    return $left ?? $right;
}

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

---

Q9 — Binary Tree Right Side View

🧠 How to Approach This

Step 1 — Recognize the pattern: BFS — take last node at each level.

Step 2 — Brute force (what NOT to do): DFS with level tracking — works but BFS is more direct.

Step 3 — Optimal insight: During BFS, record the last node in each level batch.

Step 4 — Algorithm:

1. BFS level-order

2. At i === size-1 → append to result

Step 5 — Edge cases: Left-skewed tree shows left nodes; empty tree → [].

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)

---

Q10 — Count Good Nodes in Binary Tree

🧠 How to Approach This

Step 1 — Recognize the pattern: Track max value on path from root; node is "good" if val ≥ max.

Step 2 — Brute force (what NOT to do): Store entire path — O(h) space per call.

Step 3 — Optimal insight: Pass running max down; increment counter at each good node.

Step 4 — Algorithm:

1. DFS(node, maxSoFar)

2. If node.val >= maxSoFar → count++; update max

3. Recurse left and right with updated max

Step 5 — Edge cases: Root is always good.

function goodNodes(?TreeNode $root): int {
    return dfsGood($root, PHP_INT_MIN);
}
function dfsGood(?TreeNode $node, int $maxSoFar): int {
    if ($node === null) return 0;
    $good = ($node->val >= $maxSoFar) ? 1 : 0;
    $max  = max($maxSoFar, $node->val);
    return $good + dfsGood($node->left, $max) + dfsGood($node->right, $max);
}

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

---

Q11 — Kth Smallest in BST

🧠 How to Approach This

Step 1 — Recognize the pattern: Inorder traversal of BST gives sorted order; stop at kth element.

Step 2 — Brute force (what NOT to do): Collect all inorder values then index — O(n) space.

Step 3 — Optimal insight: Iterative inorder with early exit when counter hits k.

Step 4 — Algorithm:

1. Iterative inorder with stack

2. Decrement k on each pop; when k === 0 → return value

Step 5 — Edge cases: k = 1 (minimum); k = n (maximum).

function kthSmallest(?TreeNode $root, int $k): int {
    $stack = [];
    $curr  = $root;
    while ($curr !== null || !empty($stack)) {
        while ($curr !== null) { $stack[] = $curr; $curr = $curr->left; }
        $curr = array_pop($stack);
        if (--$k === 0) return $curr->val;
        $curr = $curr->right;
    }
    return -1;
}

Time: O(h + k) | Space: O(h)

---

Q12 — Binary Tree Maximum Path Sum

🧠 How to Approach This

Step 1 — Recognize the pattern: At each node, max path through it = node + max(0, left gain) + max(0, right gain).

Step 2 — Brute force (what NOT to do): Try all pairs of nodes as endpoints — O(n²).

Step 3 — Optimal insight: Post-order DFS; track global max; return only one side (left or right) to parent.

Step 4 — Algorithm:

1. gain(node) = node.val + max(0, gain(left)) + max(0, gain(right)) → update global max

2. Return node.val + max(0, max(gain(left), gain(right)))

Step 5 — Edge cases: All negative values; single node.

function maxPathSum(?TreeNode $root): int {
    $max = PHP_INT_MIN;
    $gain = function(?TreeNode $node) use (&$gain, &$max): int {
        if ($node === null) return 0;
        $l = max(0, $gain($node->left));
        $r = max(0, $gain($node->right));
        $max = max($max, $node->val + $l + $r);
        return $node->val + max($l, $r);
    };
    $gain($root);
    return $max;
}

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

---

Q13 — Serialize and Deserialize Binary Tree

🧠 How to Approach This

Step 1 — Recognize the pattern: Preorder DFS + null markers for structure; split and rebuild on deserialize.

Step 2 — Brute force (what NOT to do): Level-order with position indices — complex for sparse trees.

Step 3 — Optimal insight: Preorder "val,#,#" format is self-describing; recurse on token list.

Step 4 — Algorithm:

1. Serialize: DFS preorder, use "#" for null, join with ","

2. Deserialize: split, maintain pointer, recurse

Step 5 — Edge cases: Empty tree → "#"; single node → "1,#,#".

function serialize(?TreeNode $root): string {
    if ($root === null) return '#';
    return $root->val . ',' . serialize($root->left) . ',' . serialize($root->right);
}
function deserialize(string $data): ?TreeNode {
    $tokens = explode(',', $data);
    $idx    = 0;
    $build  = function() use (&$build, &$tokens, &$idx): ?TreeNode {
        $val = $tokens[$idx++];
        if ($val === '#') return null;
        $node        = new TreeNode((int)$val);
        $node->left  = $build();
        $node->right = $build();
        return $node;
    };
    return $build();
}

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

---

Q14 — Construct Tree from Preorder + Inorder

🧠 How to Approach This

Step 1 — Recognize the pattern: Preorder[0] is root; find it in inorder to split left/right subtrees.

Step 2 — Brute force (what NOT to do): Linear scan for root in inorder at each level — O(n²).

Step 3 — Optimal insight: Hash map of inorder indices for O(1) lookup.

Step 4 — Algorithm:

1. Build index map from inorder

2. build(preL, preR, inL, inR): preorder[preL] is root

3. rootIdx = map[root.val]; leftSize = rootIdx - inL

4. Recurse for left and right

Step 5 — Edge cases: Single element; all left or all right children.

function buildTree(array $preorder, array $inorder): ?TreeNode {
    $map = array_flip($inorder);
    $build = function(int $preL, int $preR, int $inL, int $inR)
             use (&$build, &$preorder, &$map): ?TreeNode {
        if ($preL > $preR) return null;
        $rootVal  = $preorder[$preL];
        $node     = new TreeNode($rootVal);
        $rootIdx  = $map[$rootVal];
        $leftSize = $rootIdx - $inL;
        $node->left  = $build($preL + 1, $preL + $leftSize, $inL, $rootIdx - 1);
        $node->right = $build($preL + $leftSize + 1, $preR, $rootIdx + 1, $inR);
        return $node;
    };
    return $build(0, count($preorder) - 1, 0, count($inorder) - 1);
}

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

---

Q15 — Flatten Binary Tree to Linked List

🧠 How to Approach This

Step 1 — Recognize the pattern: Preorder traversal order; right pointer becomes "next", left pointer set to null.

Step 2 — Brute force (what NOT to do): Collect preorder nodes in array, rewire — O(n) space.

Step 3 — Optimal insight: Morris-like: find rightmost of left subtree, attach right subtree there, move left to right.

Step 4 — Algorithm:

1. While root not null:

2. If left: find rightmost of left subtree → attach root.right there → root.right = root.left; root.left = null

3. Advance root = root.right

Step 5 — Edge cases: No left child; single node.

function flatten(?TreeNode $root): void {
    $curr = $root;
    while ($curr !== null) {
        if ($curr->left !== null) {
            $prev = $curr->left;
            while ($prev->right !== null) $prev = $prev->right;
            $prev->right = $curr->right;
            $curr->right = $curr->left;
            $curr->left  = null;
        }
        $curr = $curr->right;
    }
}

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

---

Q16 — Diameter of Binary Tree

🧠 How to Approach This

Step 1 — Recognize the pattern: Diameter through a node = height(left) + height(right); track max globally.

Step 2 — Brute force (what NOT to do): Compute height for each node separately — O(n²).

Step 3 — Optimal insight: Combine height computation with diameter tracking in one DFS.

Step 4 — Algorithm:

1. DFS returns height; at each node update max with l+r

2. Return 1 + max(l, r) to parent

Step 5 — Edge cases: Single node → 0; path doesn't have to pass through root.

function diameterOfBinaryTree(?TreeNode $root): int {
    $max = 0;
    $depth = function(?TreeNode $node) use (&$depth, &$max): int {
        if ($node === null) return 0;
        $l = $depth($node->left);
        $r = $depth($node->right);
        $max = max($max, $l + $r);
        return 1 + max($l, $r);
    };
    $depth($root);
    return $max;
}

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

---

Q17 — Balanced Binary Tree

🧠 How to Approach This

Step 1 — Recognize the pattern: Return -1 as sentinel for unbalanced; otherwise return height.

Step 2 — Brute force (what NOT to do): Compute height separately for each node — O(n²).

Step 3 — Optimal insight: Post-order DFS; propagate -1 upward immediately on imbalance.

Step 4 — Algorithm:

1. check(node): if null return 0

2. left = check(left); if -1 return -1

3. right = check(right); if -1 return -1

4. if |l-r| > 1 return -1; else return 1 + max(l,r)

Step 5 — Edge cases: Empty tree → true.

function isBalanced(?TreeNode $root): bool {
    return checkBal($root) !== -1;
}
function checkBal(?TreeNode $node): int {
    if ($node === null) return 0;
    $l = checkBal($node->left);  if ($l === -1) return -1;
    $r = checkBal($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)

---

Q18 — Sum Root to Leaf Numbers

🧠 How to Approach This

Step 1 — Recognize the pattern: Pass accumulated number down; at leaf add to total.

Step 2 — Brute force (what NOT to do): Store all paths as strings, parse — O(n·h) space.

Step 3 — Optimal insight: Pass current number = prev * 10 + node.val; total at leaf.

Step 4 — Algorithm:

1. dfs(node, current = 0): current = current*10 + val

2. If leaf → return current

3. Return dfs(left, current) + dfs(right, current)

Step 5 — Edge cases: Empty tree → 0; single node → its value.

function sumNumbers(?TreeNode $root): int {
    $dfs = function(?TreeNode $node, int $curr) use (&$dfs): int {
        if ($node === null) return 0;
        $curr = $curr * 10 + $node->val;
        if ($node->left === null && $node->right === null) return $curr;
        return $dfs($node->left, $curr) + $dfs($node->right, $curr);
    };
    return $dfs($root, 0);
}

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

---

Q19 — Path Sum II (All Paths)

🧠 How to Approach This

Step 1 — Recognize the pattern: Backtracking DFS — add node to path, recurse, then remove.

Step 2 — Brute force (what NOT to do): Copy array at each node — O(n·h) space.

Step 3 — Optimal insight: Mutate single path array; push before recurse, pop after.

Step 4 — Algorithm:

1. dfs(node, remaining, path, result)

2. Push node.val; if leaf and remaining==0 → add copy to result

3. Recurse left/right; pop path

Step 5 — Edge cases: No valid paths → return [].

function pathSum(?TreeNode $root, int $targetSum): array {
    $result = [];
    $dfs = function(?TreeNode $node, int $rem, array &$path) use (&$dfs, &$result): void {
        if ($node === null) return;
        $path[] = $node->val;
        $rem   -= $node->val;
        if ($node->left === null && $node->right === null && $rem === 0)
            $result[] = $path;
        $dfs($node->left,  $rem, $path);
        $dfs($node->right, $rem, $path);
        array_pop($path);
    };
    $path = [];
    $dfs($root, $targetSum, $path);
    return $result;
}

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

---

Q20 — Convert Sorted Array to BST

🧠 How to Approach This

Step 1 — Recognize the pattern: Middle element becomes root → guarantees balance; recurse on halves.

Step 2 — Brute force (what NOT to do): Insert elements one by one — O(n log n), potentially unbalanced.

Step 3 — Optimal insight: Divide-and-conquer with mid = (l+r)/2 as root.

Step 4 — Algorithm:

1. build(l, r): if l > r return null

2. mid = (l + r) >> 1; create node

3. left = build(l, mid-1); right = build(mid+1, r)

Step 5 — Edge cases: Empty array → null; single element → leaf.

function sortedArrayToBST(array $nums): ?TreeNode {
    $build = function(int $l, int $r) use (&$build, &$nums): ?TreeNode {
        if ($l > $r) return null;
        $mid  = ($l + $r) >> 1;
        $node = new TreeNode($nums[$mid]);
        $node->left  = $build($l,      $mid - 1);
        $node->right = $build($mid + 1, $r);
        return $node;
    };
    return $build(0, count($nums) - 1);
}

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

---

Q21 — Binary Tree Zigzag Level Order

🧠 How to Approach This

Step 1 — Recognize the pattern: BFS level-order; alternate direction each level.

Step 2 — Brute force (what NOT to do): Two separate queues for odd/even levels — complex.

Step 3 — Optimal insight: BFS + toggle flag; array_reverse on odd levels.

Step 4 — Algorithm:

1. BFS with level batch

2. Toggle leftToRight; if false → array_reverse(level)

Step 5 — Edge cases: Single node → no reversal needed.

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

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

---

Q22 — Delete Node in BST

🧠 How to Approach This

Step 1 — Recognize the pattern: Three cases: leaf, one child, two children (replace with inorder successor).

Step 2 — Brute force (what NOT to do): Rebuild BST from scratch — O(n).

Step 3 — Optimal insight: Recurse to find node; on deletion with two children, replace val with inorder successor val then delete successor.

Step 4 — Algorithm:

1. If key < root.val → recurse left; if key > root.val → recurse right

2. Found: leaf → null; one child → return that child

3. Two children: find leftmost of right subtree (min), replace val, delete that node

Step 5 — Edge cases: Key not in tree; root deletion.

function deleteNode(?TreeNode $root, int $key): ?TreeNode {
    if ($root === null) return null;
    if ($key < $root->val)      $root->left  = deleteNode($root->left,  $key);
    else if ($key > $root->val) $root->right = deleteNode($root->right, $key);
    else {
        if ($root->left  === null) return $root->right;
        if ($root->right === null) return $root->left;
        $succ = $root->right;
        while ($succ->left !== null) $succ = $succ->left;
        $root->val   = $succ->val;
        $root->right = deleteNode($root->right, $succ->val);
    }
    return $root;
}

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

---

Q23 — Binary Tree Level Order Bottom-Up

🧠 How to Approach This

Step 1 — Recognize the pattern: Standard BFS level-order, then reverse the result array.

Step 2 — Brute force (what NOT to do): DFS with depth tracking and sort — more complex.

Step 3 — Optimal insight: BFS + array_reverse at the end.

Step 4 — Algorithm:

1. Standard level-order BFS into result

2. Return array_reverse(result)

Step 5 — Edge cases: Empty tree → [].

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

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

---

Q24 — Recover Binary Search Tree

🧠 How to Approach This

Step 1 — Recognize the pattern: Inorder traversal of BST is sorted; exactly two nodes are swapped — find them.

Step 2 — Brute force (what NOT to do): Collect all nodes, sort, reinsert — O(n log n).

Step 3 — Optimal insight: Inorder traversal tracking prev; first inversion = first bad node; second inversion = second bad node.

Step 4 — Algorithm:

1. Inorder DFS tracking prev

2. First violation: first = prev, second = curr

3. Subsequent violation: update second only

4. Swap first.val and second.val

Step 5 — Edge cases: Adjacent nodes swapped (only one inversion visible).

function recoverTree(?TreeNode $root): void {
    $first = $second = $prev = null;
    $inorder = function(?TreeNode $node) use (&$inorder, &$first, &$second, &$prev): void {
        if ($node === null) return;
        $inorder($node->left);
        if ($prev !== null && $prev->val > $node->val) {
            if ($first === null) $first = $prev;
            $second = $node;
        }
        $prev = $node;
        $inorder($node->right);
    };
    $inorder($root);
    [$first->val, $second->val] = [$second->val, $first->val];
}

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

---

Q25 — Maximum Width of Binary Tree

🧠 How to Approach This

Step 1 — Recognize the pattern: BFS with position indices; width = rightmost − leftmost + 1 at each level.

Step 2 — Brute force (what NOT to do): Track null nodes in queue — exponential space for sparse trees.

Step 3 — Optimal insight: Index nodes as in a heap (left=2i+1, right=2i+2); normalize per level to prevent overflow.

Step 4 — Algorithm:

1. BFS queue of [node, index] pairs

2. Per level: width = last.index − first.index + 1

3. Normalize by subtracting level's first index

Step 5 — Edge cases: Single node per level → width 1; highly unbalanced trees.

function widthOfBinaryTree(?TreeNode $root): int {
    if ($root === null) return 0;
    $maxWidth = 0;
    $queue    = [[$root, 0]];
    while (!empty($queue)) {
        $size    = count($queue);
        $offset  = $queue[0][1];
        $first   = $last = 0;
        $nextQ   = [];
        for ($i = 0; $i < $size; $i++) {
            [$node, $idx] = $queue[$i];
            $idx -= $offset;
            if ($i === 0)      $first = $idx;
            if ($i === $size-1) $last  = $idx;
            if ($node->left)  $nextQ[] = [$node->left,  2 * $idx];
            if ($node->right) $nextQ[] = [$node->right, 2 * $idx + 1];
        }
        $maxWidth = max($maxWidth, $last - $first + 1);
        $queue    = $nextQ;
    }
    return $maxWidth;
}

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