CODEWITHSUNDEEP
algorithmbinary-treebinary-search-tree
Manu
Manu

Reputation: 73

Finding Time complexity of constructing Binary Search Tree

Suppose we have in-order traversal order and post-order traversal with us. for example: in-order: 30 40 45 50 65 70 80 Post-order: 30 45 40 65 80 70 50

I know how to construct a Binary Search Tree from given in-order traversal and post-order traversal, but my question is what will be the average and worst case time complexity of B.S.T construction if a post-order traversal is given?

Upvotes: 2

Views: 2397

Answers (2)

Juan Lopes
Juan Lopes

Reputation: 10565

You can construct the tree using the post-order traversal in O(n) using the following rationale:

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

The construction from in-order is even more trivial. You just have to pick the middle element as root and call it recursively on both sides.

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

from collections import deque

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 visit_post_order(in_queue, limit = None):
    if len(in_queue) == 0 or in_queue[-1] < limit:
        return None
    root = in_queue.pop()
    right = visit_post_order(in_queue, max(root, limit))
    left = visit_post_order(in_queue, limit)

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

def visit_in_order(in_order, begin, end):
    if begin==end: return None
    if begin+1==end: return in_order[begin]

    mid = (begin+end)/2
    root = in_order[mid]
    left = visit_in_order(in_order, begin, mid)
    right = visit_in_order(in_order, mid+1, end)

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

def from_post_order(post_order):
    return visit_post_order(deque(post_order))

def from_in_order(in_order):
    return visit_in_order(in_order, 0, len(in_order))

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

Run like this:

python test.py | dot -Tpng | display

And you'll have a nice tree output:

tree

Upvotes: 0

jan_kowalski_314
jan_kowalski_314

Reputation: 84

In both cases for naive BST constructing algorithm it will be time O(n^2), because:

in in-order case the algorithm will be adding to the right

in post-order case the algorithm will be adding to the left side

So T(n) = 1 + 2 + 3 + ... n-1 = O(n^2)

UPDATE_3: But in post-order case we can simply add every next element as a root (previous tree becomes left son), so the complexity is O(n)

UPDATE: Of course the average time for a permutation of numbers is O(n logn), but in those cases this time is O(n^2) (n is number of numbers)

UPDATE_2: For more details look at the comments at the bottom.

Upvotes: 1

Related Questions