What is the time complexity to construct binary search tree when inorder and postorder traversal of tree is given?

a)
O(n)

b)
O( n log n )

c)
O(n²)

d)
O(n²log n)

Correct answer is option 'C'. Can you explain this answer?

Question

What is the time complexity to construct binary search tree when inorder and postorder traversal of tree is given?

a)
O(n)
b)
O( n log n )
c)
O(n²)
d)
O(n²log n)

Correct answer is option 'C'. Can you explain this answer?

Answer

Understanding the Problem
To construct a Binary Search Tree (BST) from given inorder and postorder traversals, we need to identify the root and recursively build the left and right subtrees.
Traversal Properties
- Inorder Traversal: This gives the sorted order of elements in a BST.
- Postorder Traversal: This helps identify the root of the tree.
Construction Process
1. Identify the Root: The last element in the postorder array is the root of the current subtree.
2. Find Root's Index: Using the inorder array, find the index of this root element. This divides the inorder array into left and right subtrees.
3. Recursive Construction: Recursively repeat the process for the left and right subtrees.
Time Complexity Analysis
- Finding the Root: For each node, we need to search its index in the inorder array, which takes O(n) time in the worst case.
- Recursive Calls: There are n nodes to process, and if we perform a linear search for each node, the total time taken becomes O(n^2) due to the nested nature of the search within the recursive structure.
Conclusion
Thus, the overall time complexity for constructing the BST from the given inorder and postorder traversals is O(n^2), making option 'C' the correct answer.
This complexity arises primarily from the repeated search operations within the inorder array for each node in the postorder array.

Similar GATE Doubts

Which of the following traversal is sufficient to construct Binary search tree from traversal?I. PreorderII. InorderIII. Postorder

Which one of the following is the tightest upper bound that represents the time complexity ofinserting an object into a binary search tree of n nodes?

What is the complexity of the efficient algorithm to construct a balanced BST from a given normal BST?

Consider the following Binary search tree with the following traversalsInorder:A, M, N, O, P, Q, R, S, T, X, ZPreorder:Q, P, A, M, N, O, X, S, R, T, ZFind the number of elements in the 4th, 5thand 6thlevel respectively. Assume root is at level 1.

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42.Which one of the following is the postorder traversal sequence of the same tree?

Top Courses for GATE

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Other Engg Branches

Related Exams

Company