Construct a BST from its postorder traversal
Filed under Amazon
Free read 3 of 3Distinct values, an empty traversal returns None, and the BST is uniquely determined by its postorder traversal.
The question
Given the postorder traversal of a binary search tree with distinct values, write clean code that rebuilds the BST and returns its root.
Constraints
- 1 <= number of nodes <= 1000
- All node values are distinct
Examples
- Input
- [1,3,2,5,7,6,4]
- Output
- Tree with root 4, left 2 (1,3), right 6 (5,7)
- Why
- Its preorder is [4,2,1,3,6,5,7].
Approach
Distinct values, an empty traversal returns None, and the BST is uniquely determined by its postorder traversal.
The last element is the root. Find the first element greater than the root: elements before it form the left subtree, the rest (except the root) form the right. Recurse. This is O(n^2) in skewed trees because of the scans.
Postorder is left, right, root, so read from the end: root, then right subtree, then left. Recurse with valid (low, high) bounds, consuming an element only if it lies within the bounds. Build the right subtree before the left.
Empty list, single node, fully left or right skewed tree. O(n) time, O(h) recursion space. Verify by checking preorder or inorder output.
Solution
O(n) time, O(h) space
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
class Solution:
def buildBST(self, postorder):
idx = [len(postorder) - 1] # read postorder from the end
def build(lo, hi):
if idx[0] < 0 or not (lo < postorder[idx[0]] < hi):
return None
v = postorder[idx[0]]; idx[0] -= 1
node = TreeNode(v)
node.right = build(v, hi) # right subtree comes first
node.left = build(lo, v)
return node
return build(float('-inf'), float('inf'))
def preorder(n):
return [] if not n else [n.val] + preorder(n.left) + preorder(n.right)
Tips
- What they are testing: Understanding traversal order and BST bounds so you can build the tree in a single pass.
- Common mistake: Building the left subtree before the right when scanning from the end, which assigns nodes to the wrong side.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.