You are given the postorder traversal, P, of a binary search tree on the n…

Answer: O(n)

Why this is unique and reconstructible:

• For a BST on keys 1..n, the inorder traversal is the sorted sequence 1,2,...,n.

• Given inorder and postorder traversals, a binary tree is uniquely determined. Here inorder is known implicitly, so postorder suffices to reconstruct the unique BST.

Algorithm (linear-time reconstruction):

• Let post be the given postorder array and set postIndex = n-1 (index of last element).

• Define a recursive function build(left, right) that builds the subtree whose inorder values range from left to right (inclusive). If left > right, return null.

• In each call, take rootVal = post[postIndex] and decrement postIndex. The inorder index of rootVal is rootVal itself (or rootVal - 1 if using 0-based indices), because inorder is 1..n.

• Build the right subtree by calling build(rootIndex+1, right), then build the left subtree with build(left, rootIndex-1), and attach them to the root node. Return the root.

• Call build(1, n) to reconstruct the entire tree.

Complexity:

• Time: Each node is created and processed exactly once with O(1) work per node, so the algorithm runs in O(n) time.

• Space: O(n) for the tree itself and O(h) recursion stack where h is tree height (worst-case O(n)).