Construct BST from given preorder traversal, traversal in binary search tree(bst) Pre-Order Traversal

        i.            Pre-order Traversal -

·        In this traversal method, the root node is visited first, then the left sub tree and finally the Right sub tree.

               

·        We start from A, and following pre-order traversal, we first visit A itself and then move to its left sub tree B.

·        B is also traversed pre-order. The process goes on until all the nodes

are visited.

 The output of pre-order traversal of this tree will be −

A → B → D → E → C → F → G

Algorithm

Until all nodes are traversed −

Step 1 − Visit root node.

Step 2 − Recursively traverse left sub tree.

Step 3 − Recursively traverse right sub tree.