Binary Search Tree (BST) - Construct from Preorder Traversal Array

 Binary search tree or BST is a hierarchical data structure which can be traversed in more than one ways. Preorder traversal is one of the way in which we can traverse a binary tree. In this article we will discuss how we can create a new Binary Search Tree if we are given an array of its keys generated by Preorder traversal (Root, Left, Right) of the tree.

You can visit this link to understand the Preorder traversal along with other depth first traversal strategies of BST - BST Depth First Traversal Strategies (Inorder, Preorder, Postorder).

We will use recursive approach for BST construction from preorder array.

Explanation - Suppose we are given this preorder array - {10, 5, 1, 7, 40, 30, 50}.
For better understanding refer the BST figure given below -

We already know that in preordrer traversal the order is (Root, Left, Right) for each sub tree, the given array basically represents the overall tree so its very first node would be the root node of the tree obviously. And the next element would be the root of its left subtree and also the left node. Now if the tree had only three nodes (root node-10, left node of root-5, right node of root-40) then it would have been very easy for us to get the right node also which would have been the element at index 2 of the array (40). But since left node can have further children elements (left and right nodes and their children) we can not be sure that third element in the array is the right node. 

But there is one thing we can be sure about that the very next element after root node is the left node and after that the next upcoming element which is greater than than the root node is right node of the root node.
So basically all the nodes starting from the left node till the right node index-1 represents the left sub tree of the root node and elements starting from right node till the end of the array represents the right sub tree of the root node. This condition would be true for all the sub trees, so basically we can always split the array into two sub arrays based on the right node until we reach the end of the array.
Based on the same approach we have implemented our method createNode() below dividing the array into smaller sub arrays recursively and finally returning the root node of the tree.

Implementation -

package ds.tree;

import ds.tree.BStree.Node;

public class TreeFromPreorderUtil {
	
	private static Node createNode(int arr[], int left, int right) {
		
		if(left > right)
	            return null;
		
		Node root = new Node(arr[left]);
		int i;
		for(i = left; i<= right; i++) {
		    if(arr[i] > root.data)
			break;
		}
		
		root.left = createNode(arr, left+1, i-1);
		root.right= createNode(arr, i, right);
		return root;
	}
	
	public static BStree createBstFromPreorder(int arr[]) {
		Node root = createNode(arr, 0, arr.length-1);
		return new BStree(root);
	}
}

Binary Search Tree (BStree.java) -

package ds.tree;

public class BStree {

	private Node root;

	public BStree(int rootData) {
		this.root = new Node(rootData);
	}
	
	public BStree(Node root) {
		this.root = root;
	}

	static class Node {
		int data;
		Node left;
		Node right;

		public Node(int data) {
			this.data = data;
		}
	}
	
	public void printInOrder() {
		inOrderRec(this.root);
	}
	
	private void inOrderRec(Node root){
		if(root == null)
			return;
		inOrderRec(root.left);
		System.out.print(root.data + " ");
		inOrderRec(root.right);
	}
	
	public void printPreOrder() {
		preOrderRec(this.root);
	}
	
	private void preOrderRec(Node root) {
		if(root == null)
			return;
		System.out.print(root.data + " ");
		preOrderRec(root.left);
		preOrderRec(root.right);
	}
}

Now lets write a main method to use our implementation. Above we have provided the implementation of a custom binary search tree which has methods to print it in preorder and inorder manner.
Input preorder array - {10, 5, 1, 7, 40, 30, 50} Main Class -

package ds.tree;

public class CreateBSTMain {
	
	public static void main(String[] args) {
		int preOrderArr [] = {10, 5, 1, 7, 40, 30, 50};
		BStree bst = TreeFromPreorderUtil.createBstFromPreorder(preOrderArr);
		bst.printPreOrder();
		System.out.println("\nInOrder");
		bst.printInOrder();
	}
}

Output :
PreOrder
10 5 1 7 40 30 50 
InOrder
1 5 7 10 30 40 50