3.15

Observation. An in-order walk of any binary-search tree (BST) lists the keys in strictly increasing order.

Algorithm (overall [math]O(n)[/math]).
1. Collect nodes in sorted order.    Do an in-order traversal of the given tree and append each visited node pointer into an array A[0..n-1].    Cost: touches every node once → [math]O(n)[/math].
2. Build a balanced tree from the array.    Recursively choose the middle element of each sub-array as root, the left half as its left subtree and the right half as its right subtree.

Build(l, r): if l > r: return null m = ⌊(l + r) / 2⌋ root = A[m] root.left = Build(l, m - 1) root.right = Build(m + 1, r) return root

   Initial call: Build(0, n-1).    Each node is processed once → [math]O(n)[/math].

Correctness. By construction, every node’s left subtree contains only smaller keys and the right subtree only larger keys, so the result is a BST. Because the two halves of any sub-array differ in size by at most one, the heights of the left and right subtrees of every node differ by at most one → the tree is height-balanced.

Complexities. Time: in-order collection + balanced build = [math]O(n)[/math]. Extra space: the array holds n pointers → [math]Θ(n)[/math] (the original nodes are reused, no new node objects allocated).

Back to Chapter 3