Home » Technical Interview Questions » Tree Interview Questions » Construct BST from given Preorder Traversal

Construct BST from given Preorder Traversal


Reading Time - 8 mins

Given a pre-order traversal of a Binary Search Tree(BST), write an algorithm to construct the BST from given preorder traversal.

Examples

Input  
preOrder[] = {7, 5, 3, 6, 9}
Output

Construct BST from given Preorder Traversal

Inorder : 3 5 6 7 9

Input
preOrder[] = {12, 6, 1, 35, 20}
Output

Construct BST from given Preorder Traversal

Inorder : 1 6 12 20 35

Naive Approach

We can see that the first element in the pre-order traversal is always the root of the tree and the rest of the elements are a part of the left and right sub-tree. As the tree is BST, so all the elements smaller than root are present in the left sub-tree, and elements greater than root are present in the right sub-tree.

So we traverse in the given array and find the first element greater than the root. Now the elements before this element(except root) is the pre-order traversal of left sub-tree and elements after this element(included it) is the pre-order traversal of right sub-tree.

So, the first element forms the root of BST, elements from index 1 to (i – 1) forms the left sub-tree, and elements from index i to (n – 1) forms the right sub-tree.

createBST(preOrder, low, high)

  1. The first element(preOrder[low]) in the array is the root of BST. If low is equals to high, return root.
  2. Traverse the array from index low + 1(0 based indexing) to high and find the first element greater than the root, let its index be i.
  3. Recursively call this method for elements from the index (low + 1) to (i – 1) and assign the BST formed to the left of root.
  4. Recursively call this method for elements from index i to high and assign the BST formed to the right of root.
  5. Return root.

Time Complexity = O(n2)
Space Complexity = O(n), due to recursion
where n is the size of the given pre-order array.

JAVA Code for Construct BST from given Preorder Traversal

public class ConstructBSTFromGivenPreorderTraversal {
    // class representing Node of BST
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // function to print inorder of a Binary Tree
    private static void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    private static Node createBST(int[] preOrder, int low, int high) {
        // if there is only 1 node in the tree, this is root, return it
        if (low == high) {
            return new Node(preOrder[low]);
        }

        // the first node is the root of the BST
        Node root = new Node(preOrder[low]);

        // find the index of first element greater than root
        int index = -1;
        for (int i = low + 1; i <= high; i++) {
            if (preOrder[i] > preOrder[low]) {
                index = i;
                break;
            }
        }

        // if all the elements are smaller than root, they forms the left subtree
        // and right subtree is null
        if (index == -1) {
            root.left = createBST(preOrder, low + 1, high);
            root.right = null;
        }
        // else elements from index (low + 1) to (index - 1) forms  the left subtree
        // and elements from index 'index' to high forms the right subtree
        else {
            root.left = createBST(preOrder, low + 1, index - 1);
            root.right = createBST(preOrder, index, high);
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int preOrder1[] = new int[] {7, 5, 3, 6, 9};
        Node root1 = createBST(preOrder1, 0, preOrder1.length - 1);
        inorder(root1);
        System.out.println();

        // Example 2
        int preOrder2[] = new int[] {12, 6, 1, 35, 20};
        Node root2 = createBST(preOrder2, 0, preOrder2.length - 1);
        inorder(root2);
        System.out.println();
    }
}
3 5 6 7 9 
1 6 12 20 35

C++ Code for Construct BST from given Preorder Traversal

#include <iostream> 
#include<vector> 
#include<queue> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
}; 

// function to print the in-order traversal of a binary tree 
void inOrder(Node *root) { 
    if (root != NULL) { 
        inOrder(root->left); 
        cout<<root->data<<" "; 
        inOrder(root->right); 
    } 
} 

Node* createBST(int *preOrder, int low, int high) {
    // if there is only 1 node in the tree, this is root, return it
    if (low == high) {
        return new Node(preOrder[low]);
    }
    
    // the first node is the root of the BST
    Node *root = new Node(preOrder[low]);
    
    // find the index of first element greater than root
    int index = -1;
    for (int i = low + 1; i <=high; i++) {
        if (preOrder[i] > preOrder[low]) {
            index = i;
            break;
        }
    }
    
    // if all the elements are smaller than root, they forms the left subtree
    // and right subtree is null
    if (index == -1) {
        root->left = createBST(preOrder, low + 1, high);
        root->right = NULL;
    }
    // else elements from index (low + 1) to (index - 1) forms  the left subtree
    // and elements from index 'index' to high forms the right subtree
    else {
        root->left = createBST(preOrder, low + 1, index - 1);
        root->right = createBST(preOrder, index, high);
    }
    
    // return root
    return root;
}

int main() {
    // Example 1
    int preOrder1[] = {7, 5, 3, 6, 9};
    Node *root1 = createBST(preOrder1, 0, (sizeof(preOrder1) / sizeof(preOrder1[0])) - 1);
    inOrder(root1);
    cout<<endl;

    // Example 2
    int preOrder2[] = {12, 6, 1, 35, 20};
    Node *root2 = createBST(preOrder2, 0, (sizeof(preOrder2) / sizeof(preOrder2[0])) - 1);
    inOrder(root2);
    cout<<endl;
    
    return 0;
}
3 5 6 7 9 
1 6 12 20 35

Optimal Approach

Recursive Method for Construct BST from given Preorder Traversal

The optimal idea here is to use the range trick, that is, we set a range for all the nodes, the node that comes in the range forms a root of the tree.

READ  Validate Binary Search Tree

Initially, the range is -infinity(min) and +infinity(max), so the first root comes in the range and it forms a root. Then we call the same method for the left child(updated range is from min to root’s value) and for the right child(updated range is from root’s value to max).

createBST(min, max)

  1. If the value of the element at the currIndex(globally defined) is in between min and max(both not included), then it forms a root. Allocate memory and create a new node named root. Else jump to step 4.
  2. Increment currIndex and recursively call this method to form left sub-tree as, constructBST(min, root’s value).
  3. Recursively call this method to form the right subtree as, constructBST(root’s value, max).
  4. Return root.

Time Complexity = O(n)
Space Complexity = O(n)
where n is the size of the pre-order array.

JAVA Code for Construct BST from given Preorder Traversal

public class ConstructBSTFromGivenPreorderTraversal {
    // class representing Node of BST
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // globally defined currIndex integer
    private static int currIndex = 0;

    // function to print inorder of a Binary Tree
    private static void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    private static Node createBST(int[] preOrder, int min, int max) {
        if (currIndex >= preOrder.length) {
            return null;
        }

        Node root = null;

        // if current element is in between min and max
        if (preOrder[currIndex] > min && preOrder[currIndex] < max) {
            // allocate memory for it
            root = new Node(preOrder[currIndex]);
            // increment currIndex
            currIndex++;
            // make left of root as createBST(min, root's data)
            root.left = createBST(preOrder, min, root.data);
            // make right of root as createBST(root's data, max)
            root.right = createBST(preOrder, root.data, max);
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int preOrder1[] = new int[] {7, 5, 3, 6, 9};
        currIndex = 0;
        Node root1 = createBST(preOrder1, Integer.MIN_VALUE, Integer.MAX_VALUE);
        inorder(root1);
        System.out.println();

        // Example 2
        int preOrder2[] = new int[] {12, 6, 1, 35, 20};
        currIndex = 0;
        Node root2 = createBST(preOrder2, Integer.MIN_VALUE, Integer.MAX_VALUE);
        inorder(root2);
        System.out.println();
    }
}
3 5 6 7 9 
1 6 12 20 35

C++ Code for Construct BST from given Preorder Traversal

#include <bits/stdc++.h> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
}; 

// globally defined currIndex integer
int currIndex = 0;

// function to print the in-order traversal of a binary tree 
void inOrder(Node *root) { 
    if (root != NULL) { 
        inOrder(root->left); 
        cout<<root->data<<" "; 
        inOrder(root->right); 
    } 
} 

Node* createBST(int *preOrder, int min, int max, int n) {
    if (currIndex >= n) {
        return NULL;
    }
    
    Node *root = NULL;
    
    // if current element is in between min and max
    if (preOrder[currIndex] > min && preOrder[currIndex] < max) {
        // allocate memory for it
        root = new Node(preOrder[currIndex]);
        // increment currIndex
        currIndex++;
        // make left of root as createBST(min, root's data)
        root->left = createBST(preOrder, min, root->data, n);
        // make right of root as createBST(root's data, max)
        root->right = createBST(preOrder, root->data, max, n);
    }
    
    // return root
    return root;
}

int main() {
    // Example 1
    int preOrder1[] = {7, 5, 3, 6, 9};
    currIndex = 0;
    Node *root1 = createBST(preOrder1, INT_MIN, INT_MAX, sizeof(preOrder1) / sizeof(preOrder1[0]));
    inOrder(root1);
    cout<<endl;

    // Example 2
    int preOrder2[] = {12, 6, 1, 35, 20};
    currIndex = 0;
    Node *root2 = createBST(preOrder2, INT_MIN, INT_MAX, sizeof(preOrder2) / sizeof(preOrder2[0]));
    inOrder(root2);
    cout<<endl;
    
    return 0;
}
3 5 6 7 9 
1 6 12 20 35

Iterative Method

Here we use a stack to cut down the recursion and convert the optimal approach to an iterative code.

  1. The first node is the root of BST, so make the root as the first node and push it to a stack.
  2. Traverse the pre-order array from index 1(0 based indexing) and for each element, while the current element is greater than the top of stack pop out the top and store it in a variable named temp.
  3. If the temp is null(that is current element was smaller than stack’s top), make temp as the top of the stack and current element as left of temp and push the current element to the stack.
  4. Else make the current element as the right of temp and push the current element to the stack.
  5. Return root.
READ  Convert a BST to a Binary Tree such that sum of all greater keys is added to every key

Time Complexity = O(n)
Space Complexity = O(n)
where n is the size of the pre-order array.

JAVA Code for Construct BST from given Preorder Traversal

import java.util.Stack;

public class ConstructBSTFromGivenPreorderTraversal {
    // class representing Node of a Binary Tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // function to print inorder of a Binary Tree
    private static void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    private static Node createBST(int[] preOrder) {
        // the first element is the root of BST
        Node root = new Node(preOrder[0]);
        // create a stack and push root to it
        Stack<Node> stack = new Stack<>();
        stack.push(root);

        // traverse the array from index 1
        for (int i = 1; i < preOrder.length; i++) {
            // initialize temp as null
            Node temp = null;

            // while current element is greater than top of stack
            // remove top of stack and store it in temp
            while (!stack.isEmpty() && preOrder[i] > stack.peek().data) {
                temp = stack.pop();
            }

            // if temp is null
            if (temp == null) {
                // make temp as top of stack
                temp = stack.peek();
                // current element is left of temp
                temp.left = new Node(preOrder[i]);
                // add current element to stack
                stack.push(temp.left);
            } else {
                // current element is right of temp
                temp.right = new Node(preOrder[i]);
                // add current element to the stack
                stack.push(temp.right);
            }
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int preOrder1[] = new int[] {7, 5, 3, 6, 9};
        Node root1 = createBST(preOrder1);
        inorder(root1);
        System.out.println();

        // Example 2
        int preOrder2[] = new int[] {12, 6, 1, 35, 20};
        Node root2 = createBST(preOrder2);
        inorder(root2);
        System.out.println();
    }
}
3 5 6 7 9 
1 6 12 20 35

C++ Code for Construct BST from given Preorder Traversal

#include <bits/stdc++.h> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

// function to print the in-order traversal of a binary tree 
void inOrder(Node *root) { 
    if (root != NULL) { 
        inOrder(root->left); 
        cout<<root->data<<" "; 
        inOrder(root->right); 
    } 
} 

Node* createBST(int *preOrder, int n) {
    // the first element is the root of BST
    Node *root = new Node(preOrder[0]);
    // create a stack and push root to it
    stack<Node*> st;
    st.push(root);
    
    // traverse the array from index 1
    for (int i = 1; i < n; i++) {
        // initialize temp as null
        Node *temp = NULL;
        
        // while current element is greater than top of stack
        // remove top of stack and store it in temp
        while (!st.empty() && preOrder[i] > st.top()->data) {
            temp = st.top();
            st.pop();
        }
        
        // if temp is null
        if (temp == NULL) {
            // make temp as top of stack
            temp = st.top();
            // current element is left of temp
            temp->left = new Node(preOrder[i]);
            // add current element to stack
            st.push(temp->left);
        } else {
            // current element is right of temp
            temp->right = new Node(preOrder[i]);
            // add current element to the stack
            st.push(temp->right);
        }
    }
    
    // return root
    return root;
}

int main() {
    // Example 1
    int preOrder1[] = {7, 5, 3, 6, 9};
    Node *root1 = createBST(preOrder1, sizeof(preOrder1) / sizeof(preOrder1[0]));
    inOrder(root1);
    cout<<endl;

    // Example 2
    int preOrder2[] = {12, 6, 1, 35, 20};
    Node *root2 = createBST(preOrder2, sizeof(preOrder2) / sizeof(preOrder2[0]));
    inOrder(root2);
    cout<<endl;
    
    return 0;
}
3 5 6 7 9 
1 6 12 20 35

Reference1    reference2

READ  Serialize and Deserialize Binary Tree
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions