Constructing a Binary Search Tree from Preorder Traversal
constructBST:
A function meticulously designed to iterate through the preorder traversal array, leveraging a stack to maintain the construction order of the BST. It begins with creating the root node from the first element of the preorder sequence. As it progresses, the function strategically places each subsequent element, determining its rightful position as either a left or right child based on its value relative to the stack's top element. This process, characterized by popping elements from the stack to find the correct parent for the current node and pushing new nodes to the stack, ensures adherence to the BST property throughout the construction.
1class Node{
2 constructor(data){
3 this.data = data
4 this.left = null
5 this.right = null
6 }
7}
8
9function constructBST(preorder) {
10 if (preorder.length === 0) return null;
11
12 let root = new Node(preorder[0]);
13 let stack = [root];
14
15 for (let i = 1; i < preorder.length; i++) {
16 let temp = null;
17 while(stack.length !== 0 && preorder[i]> stack[stack.length - 1].data){
18 temp = stack.pop();
19 }
20
21 if(temp !== null){
22 temp.right = new Node(preorder[i]);
23 stack.push(temp.right);
24 }else {
25 stack[stack.length - 1].left = new Node(preorder[i]);
26 stack.push(stack[stack.length - 1].left);
27 }
28 }
29 return root;
30
31}
32
33let preorder = [10, 5, 1, 7, 40, 50]
34let root = constructBST(preorder);
35
36function printInorder(node) {
37 if (node === null) return;
38 printInorder(node.left);
39 console.log(node.data);
40 printInorder(node.right);
41}
42
43printInorder(root)