Given inorder and preorder (or postorder) traversal sequences of a
- binary tree
- balanced binary tree
- binary search tree
of n nodes, what is the time complexity of creating the respective unique tree.
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ Can anybody please confirm if these time complexities are correct? $\endgroup$ – vishalgoel Jan 19 '18 at 14:19
-
$\begingroup$ This surely isn’t right. The question says you need to use both sequences to reconstruct the tree, but you’re using only one. $\endgroup$ – David Richerby Feb 18 '18 at 12:51
