GATE 2008: Time Complexity of Binary Search Tree

Question

You are given the post-order traversal, P of a binary search tree on the n elements 1,2,.........,n. you have to determine the unique binary search tree that has P as its post-order traversal. what is the time complexity of the MOST EFFICIENT algorithm for doing this?

(a) theeta(logn)

(b) theeta(n)

(c) theeta(nlogn)

(d) none of the above, as tree cannot be uniquely determined

answer is (b), please explain the solution. if we have been given post-order traversal don't we need to apply sorting(O(nlogn)) to compute in-order?

No, we don't need to compute in-order. Why would we want to? In order to come up with an algorithm, try to reason why the tree should be indeed unique. — n. 1.8e9-where's-my-share m.
we have been given only post-order traversal, as we know in-order traversal is always gives a sorted list in ascending order and we need in-order and post/pre order traversal so i thought by applying sorting on post-traversal order we can get in-order — Manu Thakur
I googled the interwebs using the first paragraph of your problem statement. There is a page that explains this, but using pre-order. Are you asking for an explanation of that page which is a guide to doing it post-order? http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/ — Marichyasana

Juan Lopes Juan Lopes · Accepted Answer · 2015-08-12T06:41:52

No, you don't have to sort it.

In the post-order traversal you can find some hidden info. Like:

The last element is always the tree root
All the previous elements greater than the root are part of the right subtree. All the elements lesser are part of the left subtree.
You can apply the above rules recursively.

This is only true because you have only distinct elements. If there were repetitions, the tree for the traversal couldn't be unique.

Here's an example implementation (in Python) that shows this:

from collections import deque

def visit(in_queue, limit = None):
    if len(in_queue) == 0 or in_queue[-1] < limit:
        return None
    root = in_queue.pop()
    right = visit(in_queue, max(root, limit))
    left = visit(in_queue, limit)

    if left is None and right is None:
        return root
    else:
        return (left, root, right)

def print_graphviz(tree):
    if not isinstance(tree, tuple):
        return tree
    left = print_graphviz(tree[0])
    right = print_graphviz(tree[2])

    if left is not None: print tree[1], '->', left
    if right is not None: print tree[1], '->', right
    return tree[1]

def make_tree(post_order):
    return visit(deque(post_order))

print 'digraph {'
print print_graphviz(make_tree([0, 2, 1, 4, 3, 6, 8, 7, 5]))
print '}'

Run like this:

python test.py | dot -Tpng | display

And you'll have a nice tree output:

GATE 2008: Time Complexity of Binary Search Tree

3 Answers