Construct Binary Search Tree from Preorder Traversal
We are now solving a problem which is asked by many of the product based companies. An interviewer will ask you to construct a binary search tree using a preorder traversal array. Before we proceed with this problem, let's recall the binary search tree with below-mentioned points:- The right subtree of a node contains only nodes with keys that are greater than the node's key. The left subtree of a node contains only nodes with keys that are lesser than the node's key. We have to check on each node with the above conditions. Quadratic Solution O(n 2 ) public static TreeNode bstFromPreorder( int [] preorder) { // Initialize the treenode TreeNode treeNode = new TreeNode(); // Check if the preorder array does contain value if (preorder. length > 0 ) treeNode. val = preorder[ 0 ]; // Iterate over the 1 to preorder length for ( int i = 1 ; i < preorder. length ; i++) {