311 views
0 votes
0 votes
1.Given inorder and preorder/postorder, time taken to construct a binary tree?

2. Given inorder and preorder/postorder, time taken to construct a binary search tree?

3. why giving inorder is essential to construct binary tree along with preorder/ postorder?

1 Answer

1 votes
1 votes

1. Construct BT from inorder and pre-order is $O(n^2)$

2. Construct BT from inorder and post-order is also $O(n^2)$

3. An inorder is must to uniquely identify the tree. No other combinations like pre-order and Post order cannot find the tree. For example, the trees given below have same pre-order and post order (Ref: http://www.geeksforgeeks.org/if-you-are-given-two-traversal-sequences-can-you-construct-the-binary-tree/)

Mirror

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
3