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.

Jamnes

The inorder being given doesn't really make anything easier: just sort whatever traversal you're given and that's your inorder. – Hypotrachelium

possible duplicate of Construction of BST from given Postorder Traversal – Elasticity

Answer 1

If you have an array from a post-order traversal of a BST, you know that the root is the last element of the array. The left child of the root takes up the first part of the array, and consists of entries smaller than the root. Then follows the right child, consisting of elements larger than the root. (Both children may be empty).

________________________________
|             |              |R|
--------------------------------
 left child     right child   root

So the main problem is to find the point where the left child ends and the right begins.

Both children are also obtained from their post-order traversal, so constructing them is done in the same way, recursively.

BST fromPostOrder(value[] nodes) {
    // No nodes, no tree
    if (nodes == null) return null;
    return recursiveFromPostOrder(nodes, 0,  nodes.length - 1);
}

// Construct a BST from a segment of the nodes array
// That segment is assumed to be the post-order traversal of some subtree
private BST recursiveFromPostOrder(value[] nodes, 
                                   int leftIndex, int rightIndex) {
    // Empty segment -> empty tree
    if (rightIndex < leftIndex) return null;
    // single node -> single element tree
    if (rightIndex == leftIndex) return new BST(nodes[leftIndex]);

    // It's a post-order traversal, so the root of the tree 
    // is in the last position
    value rootval = nodes[rightIndex];

    // Construct the root node, the left and right subtrees are then 
    // constructed in recursive calls, after finding their extent
    BST root = new BST(rootval);

    // It's supposed to be the post-order traversal of a BST, so
    // * left child comes first
    // * all values in the left child are smaller than the root value
    // * all values in the right child are larger than the root value
    // Hence we find the last index in the range [leftIndex .. rightIndex-1]
    // that holds a value smaller than rootval
    int leftLast = findLastSmaller(nodes, leftIndex, rightIndex-1, rootval);

    // The left child occupies the segment [leftIndex .. leftLast]
    // (may be empty) and that segment is the post-order traversal of it
    root.left = recursiveFromPostOrder(nodes, leftIndex, leftLast);

    // The right child occupies the segment [leftLast+1 .. rightIndex-1]
    // (may be empty) and that segment is the post-order traversal of it
    root.right = recursiveFromPostOrder(nodes, leftLast + 1, rightIndex-1);

    // Both children constructed and linked to the root, done.
    return root;
}

// find the last index of a value smaller than cut in a segment of the array
// using binary search
// supposes that the segment contains the concatenation of the post-order
// traversals of the left and right subtrees of a node with value cut,
// in particular, that the first (possibly empty) part of the segment contains
// only values < cut, and the second (possibly empty) part only values > cut
private int findLastSmaller(value[] nodes, int first, int last, value cut) {

    // If the segment is empty, or the first value is larger than cut,
    // by the assumptions, there is no value smaller than cut in the segment,
    // return the position one before the start of the segment
    if (last < first || nodes[first] > cut) return first - 1;

    int low = first, high = last, mid;

    // binary search for the last index of a value < cut
    // invariants: nodes[low] < cut 
    //             (since cut is the root value and a BST has no dupes)
    // and nodes[high] > cut, or (nodes[high] < cut < nodes[high+1]), or
    // nodes[high] < cut and high == last, the latter two cases mean that
    // high is the last index in the segment holding a value < cut
    while (low < high && nodes[high] > cut) {

        // check the middle of the segment
        // In the case high == low+1 and nodes[low] < cut < nodes[high]
        // we'd make no progress if we chose mid = (low+high)/2, since that
        // would then be mid = low, so we round the index up instead of down
        mid = low + (high-low+1)/2;

        // The choice of mid guarantees low < mid <= high, so whichever
        // case applies, we will either set low to a strictly greater index
        // or high to a strictly smaller one, hence we won't become stuck.
        if (nodes[mid] > cut) {
            // The last index of a value < cut is in the first half
            // of the range under consideration, so reduce the upper
            // limit of that. Since we excluded mid as a possible
            // last index, the upper limit becomes mid-1
            high = mid-1;
        } else {
            // nodes[mid] < cut, so the last index with a value < cut is
            // in the range [mid .. high]
            low = mid;
        }
    }
    // now either low == high or nodes[high] < cut and high is the result
    // in either case by the loop invariants
    return high;
}

Cychosz

Can you please explain you algorithm a bit more? Some inline comments would do fine... – Jamnes

There you are, adding the comments even unearthed a superfluous if. – Cychosz

Won't the findLastSmaller(nodes, 0, nodes.length - 2, rootval); line be findLastSmaller(nodes, leftindex, rightindex - 2, rootval);? – Jamnes

It's rightIndex-1, since the root value sat at rightIndex. But in principle, yeah. I moved that call from the public to the recursive when deciding I didn't need to handle the root specially and forgot to adjust parameters (:blush:). – Cychosz

Exactly. Even I was thinking rightindex-1, but asked rightindex-2 just because you had mentioned nodes.length-2. (:blush) – Jamnes

I see. Thanks for spotting it, by the way. – Cychosz

What would be the time complexity of this method?? O(logn)?? – Cestus

@MohitJain O(n*log n). For every node, we need a binary search with complexity O(log n) [a sharper bound is O(log t), where t is the size of the subtree whose root is the node we're currently treating, that doesn't change the complexity, however, it only produces a constant factor]. – Cychosz

If I'm not mistaken, the time for this is T(n) = 2T(n/2) + log n, which is Theta(n) (by the master theorem). – Output

@Output If the tree was sufficiently balanced. But if we have a degenerate tree, such that every left subtree is empty, so an array n,(n-1),…,3,2,1 for example, we get Theta(n*log n). – Cychosz

@DanielFischer I should have seen that. Thanks. – Output

Answer 2

You don't really need the inorder traversal. There's a simple way to reconstruct the tree given only the post-order traversal:

1. Take the last element in the input array. This is the root.
2. Loop over the remaining input array looking for the point where the elements change from being smaller than the root to being bigger. Split the input array at that point. This can also be done with a binary search algorithm.
3. Recursively reconstruct the subtrees from those two sub-arrays.

This can easily be done either recursively or iteratively with a stack, and you can use two indices to indicate the start and end of the current sub-array rather than actually splitting the array.

Seychelles

You sir are a genius – Baucis

Answer 3

Postorder traversal goes like this:

visit left
visit right
print current.

And inorder like this:

visit left
print current
visit right

Let's take an example:

        7
     /     \
    3      10
   / \     / \
  2   5   9   12
             /
            11

Inorder is: 2 3 5 7 9 10 11 12

Postorder is: 2 5 3 9 11 12 10 7

Iterate the postorder array in reverse order and keep splitting the inorder array around where that value is. Do this recursively and that will be your tree. For example:

current = 7, split inorder at 7: 2 3 5 | 9 10 11 12

Look familiar? What is on the left is the left subtree and what is on the right is the right subtree, in a pseudo-random order as far as the BST structure is concerned. However, you now know what your root is. Now do the same for the two halves. Find the first occurrence (from the end) of an element from the left half in the postorder traversal. That will be 3. Split around 3:

current = 3, split inorder at 3: 2 | 5 ...

So you know your tree looks like this so far:

   7
 /
3

This is based on the facts that a value in the postorder traversal will always appear after its children have appeared and that a value in the inorder traversal will appear between its children values.

Hypotrachelium

Answer 4

Don't loop over anything. Last element is your Root. then taking array backwards follow insertion rules of BST.

eg:-   
given just the postorder -- 2 5 3 9 11 12 10 7



        7
         \
          10

        ----
        7
         \
          10
           \
            12
         -----
        7
         \
          10
           \
            12
           /
          11
         -------
        7
         \
          10
         /  \
        9    12
           /
          11
         --------
        7
      /  \
     3    10
    / \  /  \
   2   5 9  12
           /
          11

Mazda

This answer is somehow giving correct results but I cannot find a proof or even intuition for it. Will this always give correct answer? – Hollo

Yes. It will. Always. Just requires a little bit of realisation. – Mazda

'Don't loop over anything' - what does this mean? Ain't you looping over the same tree for each element? and what is the time complexity of it? – Scandal

Answer 5

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))

Coif