← Amazon questions
CodingReported in a candidate post, Jul 2025

Construct a BST from its postorder traversal

Filed under Amazon

Free read 3 of 3

Distinct 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

  1. Distinct values, an empty traversal returns None, and the BST is uniquely determined by its postorder traversal.

Solution

O(n) time, O(h) space

Python
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.