Time complexity of creating the unique binary tree from given inorder and preorder (or postorder) traversal sequences

Question

Given inorder and preorder (or postorder) traversal sequences of a

1. binary tree
2. balanced binary tree
3. binary search tree

of n nodes, what is the time complexity of creating the respective unique tree.

Answer 1

Assuming inorder and preorder sequences are given -

1. For binary tree : Starting with the root node, traverse the preorder sequence and for each node, binary search on the given inorder sequence, separating the left and right subtrees. Recurse on the next node with the new piece of the inorder sequence. Time complexity in worst case : T(n) = T(1) + T(n-1) + O(logn) = O(nlogn)

2. For balanced binary tree : Follow the same procedure as in 1. But, since the tree is balanced, the time complexity in worst case is different: T(n) = 2T(n/2) + O(logn) = O(n)

3. For binary search tree : Traverse the preorder sequence and at each node, keep a flag (=key of the parent node). If the next node in the sequence is less than the flag, then the node gets to be the left or right child of the current node. Else, we go back to the parent recursively and apply the same procedure to it. Time complexity = O(n) since we are creating nodes in the preorder sequence.