Construct Binary Search Tree from a given Preorder Traversal Using Stack (Without Recursion)

Objective: Given a preorder traversal, construct BST from that, without using recursion.

Input: Preorder traversal

Similar Problem : This problem is similar to the Construct Binary Search Tree from a given Preorder Traversal using Recursion.

Approach:

  • Example: int[] preOrder = { 20, 10, 5, 1, 7, 15, 30, 25, 35, 32, 40 };
  • Use Stack.
  • First element in the preorder[] will definitely be the root, which is 20 here.
  • Create a node with data 20 and push it in Stack.
  • Now take the next element (say ‘data’) from the preorder sequence.
  • If ‘data’ is greater than the top item in the stack then keep popping out the nodes from the stack, keep storing it in temp node till the top node in stack is less than the ‘data’.
  • create a node with ‘data’ and add it to the right of temp node and push the temp node to stack.
  • If ‘data’ is less than the top item in the stack then create a node with ‘data’ and add it to the left of top node in stack and push it in the stack.
  • Repeat the above two steps till all the elements in preorder[] is over.
  • return the root

Time Complexity: O(n)

Preorder Traversal To Tree Using Stack

Complete Code:

import java.util.*;
public class PreorderToTree {
public Node constructTree(int[] preorder) {
Stack<Node> s = new Stack<Node>();
Node root = new Node(preorder[0]);
s.add(root);
for (int i = 1; i < preorder.length; i++) {
Node x = null;
while (!s.isEmpty() && preorder[i] > s.peek().data) {
x = s.pop();
}
if (x != null) {
x.right = new Node(preorder[i]);
s.push(x.right);
} else {
s.peek().left = new Node(preorder[i]);
s.push(s.peek().left);
}
}
return root;
}
public void displayTree(Node root) {
if (root != null) {
displayTree(root.left);
System.out.print(" " + root.data);
displayTree(root.right);
}
}
public static void main(String args[]) {
PreorderToTree p = new PreorderToTree();
int[] preOrder = {10,5,2,7,15,12,20 };
Node root = p.constructTree(preOrder);
System.out.println("Inorder Traversal of Constructed Tree : ");
p.displayTree(root);
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
}

view raw
PreorderToTree.java
hosted with ❤ by GitHub


Output:

Inorder Traversal of Constructed Tree : 
 2 5 7 10 12 15 20