Which of the following traversals is sufficient to construct BST from ...
When we know either preorder or postorder traversal, we can construct the BST. Note that we can always sort the given traversal and get the inorder traversal. Inorder traversal of BST is always sorted.
View all questions of this test
Which of the following traversals is sufficient to construct BST from ...
Inorder, Preorder, and Postorder Traversals
Inorder, Preorder, and Postorder are three different ways to traverse a binary tree. Each traversal has its own unique characteristics and can be used to construct a binary search tree (BST) from the given traversals.
Inorder Traversal
In inorder traversal, we visit the left subtree, then the root, and finally the right subtree. In the case of a BST, the inorder traversal produces a sorted sequence of the tree's elements.
Preorder Traversal
In preorder traversal, we visit the root first, then the left subtree, and finally the right subtree. The root element is always the first element in the preorder traversal.
Postorder Traversal
In postorder traversal, we visit the left subtree, then the right subtree, and finally the root. The root element is always the last element in the postorder traversal.
Constructing a BST
To construct a BST from the given traversals, we need to understand the relationship between the traversals and the structure of the BST.
- Inorder traversal: The inorder traversal of a BST produces a sorted sequence of the tree's elements.
- Preorder traversal: The first element in the preorder traversal is always the root. The elements that come after the root in the preorder traversal correspond to the left subtree, and the elements that come before the root correspond to the right subtree.
- Postorder traversal: The last element in the postorder traversal is always the root. The elements that come before the root in the postorder traversal correspond to the left subtree, and the elements that come after the root correspond to the right subtree.
Answer Explanation
The given options are:
1) Inorder
2) Preorder
3) Postorder
To construct a BST, we need to have either the inorder traversal or the preorder traversal. This is because the inorder traversal gives us the sorted sequence of the tree's elements, and the preorder traversal gives us the root and the partitions of the left and right subtrees.
So, either option 1 or option 2 is sufficient to construct a BST.
Hence, the correct answer is option 'B' - Either 2 or 3 is sufficient.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).