How to construct BST given post-order traversal

Question

I know there are ways to construct a tree from pre-order traversal (as an array). The more common question is to construct it, given the inorder and pre-order traversals. In this case, although the inorder traversal is redundant, it definitely makes things easier. Can anybody give me an idea how to do it for a post-order traversal? Both iterative and recursive solutions are required.

I tried to do it iteratively using stack, but couldn't at all get the logic right, so got a horrible messy tree. Same went for recursion.

Answer 1

None of the answers show working code or provide time complexity analyses, not ever hammar's brilliant answer. I'm bothered by hand waving, so let's get down to little more formal business.

Hammer's solution in Python:

def from_postorder(nodes: Sequence[int]) -> BinaryTree[int]:
    def build_subtree(subtree_nodes: Sequence[int]) -> BinaryTree[int]:
        if not subtree_nodes:
            return None

        n = len(subtree_nodes)
        # Locates the insertion point for x to maintain sorted order.
        # This is the first element greater than root.
        x = bisect.bisect_left(subtree_nodes, subtree_nodes[-1], hi=n - 1)

        root = BinaryTree(subtree_nodes[-1])
        root.left = build_subtree(subtree_nodes[:x])
        # slice returns empty list if end is <= start
        root.right = build_subtree(subtree_nodes[x:n - 1])

        return root

    return build_subtree(nodes)

At each step, binary search takes log(n) time, and we reduce the problem by one element (the root). Thus, overall time complexity is nlog(n).

Alternative solution:

We create two data structures, one the inorder traversal of the BST, and the other a mapping for each node to its index in the postorder traversal sequence.

For a given range of nodes that form a subtree, the root is the one that appears last in the postorder traversal. To find the root efficiently, we map each node to its index using the mapping created before, and then find the max.

Having found the root, we do a binary search in the inorder traversal sequence; elements from the lower bound of the given range to the left of the root form its left subtree, and elements from the right of the root to the right bound of the range form its right subtree. We recurse on the left and right subtrees.

Put differently, we use the postorder traversal sequence to find the root, and the inorder traversal sequence to find the left and the right subtrees.

Time complexity: At each step, finding the root takes O(n) time. Binary search takes log(n) time. We also divide the problem into two roughly equal subproblems (worst case for full BST). Thus, T(n) <= 2 . T(n/2) + O(n) + log(n) = T(n/2) + O(n), which gives us O(n log(n)) using the Master theorem.

def from_postorder_2(nodes: Sequence[int]) -> BinaryTree[int]:
    inorder: Sequence[int] = sorted(nodes)
    index_map: Mapping[int, int] = dict([(x, i) for i, x in enumerate(nodes)])

    # The indices refer to the inorder traversal sequence
    def build_subtree(lo: int, hi: int) -> BinaryTree[int]:
        if hi <= lo:
            return None
        elif hi - lo == 1:
            return BinaryTree(inorder[lo])

        root = max(map(lambda i: index_map[inorder[i]], range(lo, hi)))
        root_node = BinaryTree(nodes[root])
        x = bisect.bisect_left(inorder, root_node.val, lo, hi)
        root_node.left = build_subtree(lo, x)
        root_node.right = build_subtree(x + 1, hi)

        return root_node

    return build_subtree(0, len(nodes))