Open In App

Construct BST from given preorder traversal | Set 1

Last Updated : 14 Dec, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Given the preorder traversal of a binary search tree, construct the BST.

Examples:

 Input: {10, 5, 1, 7, 40, 50}
Output:   10
               /   \
            5     40
          /  \       \
       1    7       50

Naive approach: To solve the problem follow the below idea:

The first element of preorder traversal is always the root. We first construct the root. Then we find the index of the first element which is greater than the root. Let the index be ‘i’. The values between root and ‘i’ will be part of the left subtree, and the values between ‘i'(inclusive) and ‘n-1’ will be part of the right subtree. Divide the given pre[] at index “i” and recur for left and right sub-trees. 

For example in {10, 5, 1, 7, 40, 50}, 10 is the first element, so we make it root. Now we look for the first element greater than 10, we find 40. So we know the structure of BST is as follows.:

             10
           /    \
{5, 1, 7}     {40, 50}

We recursively follow the above steps for subarrays {5, 1, 7} and {40, 50}, and get the complete tree.

Below is the implementation of the above approach:

C++




// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node {
public:
    int data;
    node* left;
    node* right;
};
 
// A utility function to create a node
node* newNode(int data)
{
    node* temp = new node();
 
    temp->data = data;
    temp->left = temp->right = NULL;
 
    return temp;
}
 
// A recursive function to construct Full from pre[].
// preIndex is used to keep track of index in pre[].
node* constructTreeUtil(int pre[], int* preIndex, int low,
                        int high, int size)
{
    // Base case
    if (*preIndex >= size || low > high)
        return NULL;
 
    // The first node in preorder traversal is root. So take
    // the node at preIndex from pre[] and make it root, and
    // increment preIndex
    node* root = newNode(pre[*preIndex]);
    *preIndex = *preIndex + 1;
 
    // If the current subarray has only one element, no need
    // to recur
    if (low == high)
        return root;
 
    // Search for the first element greater than root
    int i;
    for (i = low; i <= high; ++i)
        if (pre[i] > root->data)
            break;
 
    // Use the index of element found in preorder to divide
    // preorder array in two parts. Left subtree and right
    // subtree
    root->left = constructTreeUtil(pre, preIndex, *preIndex,
                                   i - 1, size);
    root->right
        = constructTreeUtil(pre, preIndex, i, high, size);
 
    return root;
}
 
// The main function to construct BST from given preorder
// traversal. This function mainly uses constructTreeUtil()
node* constructTree(int pre[], int size)
{
    int preIndex = 0;
    return constructTreeUtil(pre, &preIndex, 0, size - 1,
                             size);
}
 
// A utility function to print inorder traversal of a Binary
// Tree
void printInorder(node* node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    cout << node->data << " ";
    printInorder(node->right);
}
 
// Driver code
int main()
{
    int pre[] = { 10, 5, 1, 7, 40, 50 };
    int size = sizeof(pre) / sizeof(pre[0]);
 
      // Function call
    node* root = constructTree(pre, size);
 
    printInorder(root);
 
    return 0;
}
 
// This code is contributed by rathbhupendra


C




// C program for the above approach
#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
// A utility function to create a node
struct node* newNode(int data)
{
    struct node* temp
        = (struct node*)malloc(sizeof(struct node));
 
    temp->data = data;
    temp->left = temp->right = NULL;
 
    return temp;
}
 
// A recursive function to construct Full from pre[].
// preIndex is used to keep track of index in pre[].
struct node* constructTreeUtil(int pre[], int* preIndex,
                               int low, int high, int size)
{
    // Base case
    if (*preIndex >= size || low > high)
        return NULL;
 
    // The first node in preorder traversal is root. So take
    // the node at preIndex from pre[] and make it root, and
    // increment preIndex
    struct node* root = newNode(pre[*preIndex]);
    *preIndex = *preIndex + 1;
 
    // If the current subarray has only one element, no need
    // to recur
    if (low == high)
        return root;
 
    // Search for the first element greater than root
    int i;
    for (i = low; i <= high; ++i)
        if (pre[i] > root->data)
            break;
 
    // Use the index of element found in preorder to divide
    // preorder array in two parts. Left subtree and right
    // subtree
    root->left = constructTreeUtil(pre, preIndex, *preIndex,
                                   i - 1, size);
    root->right
        = constructTreeUtil(pre, preIndex, i, high, size);
 
    return root;
}
 
// The main function to construct BST from given preorder
// traversal. This function mainly uses constructTreeUtil()
struct node* constructTree(int pre[], int size)
{
    int preIndex = 0;
    return constructTreeUtil(pre, &preIndex, 0, size - 1,
                             size);
}
 
// A utility function to print inorder traversal of a Binary
// Tree
void printInorder(struct node* node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    printf("%d ", node->data);
    printInorder(node->right);
}
 
// Driver code
int main()
{
    int pre[] = { 10, 5, 1, 7, 40, 50 };
    int size = sizeof(pre) / sizeof(pre[0]);
 
      // Function call
    struct node* root = constructTree(pre, size);
 
     
    printInorder(root);
 
    return 0;
}


Java




// Java program to construct BST from given preorder
// traversal
 
// A binary tree node
class Node {
 
    int data;
    Node left, right;
 
    Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
class Index {
 
    int index = 0;
}
 
class BinaryTree {
 
    Index index = new Index();
 
    // A recursive function to construct Full from pre[].
    // preIndex is used to keep track of index in pre[].
    Node constructTreeUtil(int pre[], Index preIndex,
                           int low, int high, int size)
    {
 
        // Base case
        if (preIndex.index >= size || low > high) {
            return null;
        }
 
        // The first node in preorder traversal is root. So
        // take the node at preIndex from pre[] and make it
        // root, and increment preIndex
        Node root = new Node(pre[preIndex.index]);
        preIndex.index = preIndex.index + 1;
 
        // If the current subarray has only one element, no
        // need to recur
        if (low == high) {
            return root;
        }
 
        // Search for the first element greater than root
        int i;
        for (i = low; i <= high; ++i) {
            if (pre[i] > root.data) {
                break;
            }
        }
 
        // Use the index of element found in preorder to
        // divide preorder array in two parts. Left subtree
        // and right subtree
        root.left = constructTreeUtil(
            pre, preIndex, preIndex.index, i - 1, size);
        root.right = constructTreeUtil(pre, preIndex, i,
                                       high, size);
 
        return root;
    }
 
    // The main function to construct BST from given
    // preorder traversal. This function mainly uses
    // constructTreeUtil()
    Node constructTree(int pre[], int size)
    {
        return constructTreeUtil(pre, index, 0, size - 1,
                                 size);
    }
 
    // A utility function to print inorder traversal of a
    // Binary Tree
    void printInorder(Node node)
    {
        if (node == null) {
            return;
        }
        printInorder(node.left);
        System.out.print(node.data + " ");
        printInorder(node.right);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        int pre[] = new int[] { 10, 5, 1, 7, 40, 50 };
        int size = pre.length;
        Node root = tree.constructTree(pre, size);
         
        tree.printInorder(root);
    }
}
 
// This code has been contributed by Mayank Jaiswal


Python3




# A O(n^2) Python3 program for
# construction of BST from preorder traversal
 
# A binary tree node
 
 
class Node():
 
    # A constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
# constructTreeUtil.preIndex is a static variable of
# function constructTreeUtil
 
# Function to get the value of static variable
# constructTreeUtil.preIndex
def getPreIndex():
    return constructTreeUtil.preIndex
 
# Function to increment the value of static variable
# constructTreeUtil.preIndex
 
 
def incrementPreIndex():
    constructTreeUtil.preIndex += 1
 
# A recursive function to construct Full from pre[].
# preIndex is used to keep track of index in pre[[].
 
 
def constructTreeUtil(pre, low, high):
 
        # Base Case
    if(low > high):
        return None
 
    # The first node in preorder traversal is root. So take
    # the node at preIndex from pre[] and make it root,
    # and increment preIndex
    root = Node(pre[getPreIndex()])
    incrementPreIndex()
 
    # If the current subarray has only one element,
    # no need to recur
    if low == high:
        return root
 
    r_root = -1
 
    # Search for the first element greater than root
    for i in range(low, high+1):
        if (pre[i] > root.data):
            r_root = i
            break
 
    # If no elements are greater than the current root,
    # all elements are left children
    # so assign root appropriately
    if r_root == -1:
        r_root = getPreIndex() + (high - low)
 
    # Use the index of element found in preorder to divide
    # preorder array in two parts. Left subtree and right
    # subtree
    root.left = constructTreeUtil(pre, getPreIndex(), r_root-1)
 
    root.right = constructTreeUtil(pre, r_root, high)
 
    return root
 
# The main function to construct BST from given preorder
# traversal. This function mainly uses constructTreeUtil()
 
 
def constructTree(pre):
    size = len(pre)
    constructTreeUtil.preIndex = 0
    return constructTreeUtil(pre, 0, size-1)
 
 
def printInorder(root):
    if root is None:
        return
    printInorder(root.left)
    print(root.data, end=' ')
    printInorder(root.right)
 
 
# Driver code
if __name__ == '__main__':
  pre = [10, 5, 1, 7, 40, 50]
 
  root = constructTree(pre)
   
  printInorder(root)
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007) and Rhys Compton


C#




using System;
 
// C# program to construct BST from given preorder traversal
// A binary tree node
public class Node {
 
    public int data;
    public Node left, right;
 
    public Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
public class Index {
 
    public int index = 0;
}
 
public class BinaryTree {
 
    public Index index = new Index();
 
    // A recursive function to construct Full from pre[].
    // preIndex is used to keep track of index in pre[].
    public virtual Node constructTreeUtil(int[] pre,
                                          Index preIndex,
                                          int low, int high,
                                          int size)
    {
 
        // Base case
        if (preIndex.index >= size || low > high) {
            return null;
        }
 
        // The first node in preorder traversal is root. So
        // take the node at preIndex from pre[] and make it
        // root, and increment preIndex
        Node root = new Node(pre[preIndex.index]);
        preIndex.index = preIndex.index + 1;
 
        // If the current subarray has only one element, no
        // need to recur
        if (low == high) {
            return root;
        }
 
        // Search for the first element greater than root
        int i;
        for (i = low; i <= high; ++i) {
            if (pre[i] > root.data) {
                break;
            }
        }
 
        // Use the index of element found in preorder to
        // divide preorder array in two parts. Left subtree
        // and right subtree
        root.left = constructTreeUtil(
            pre, preIndex, preIndex.index, i - 1, size);
        root.right = constructTreeUtil(pre, preIndex, i,
                                       high, size);
 
        return root;
    }
 
    // The main function to construct BST from given
    // preorder traversal. This function mainly uses
    // constructTreeUtil()
    public virtual Node constructTree(int[] pre, int size)
    {
        return constructTreeUtil(pre, index, 0, size - 1,
                                 size);
    }
 
    // A utility function to print inorder traversal of a
    // Binary Tree
    public virtual void printInorder(Node node)
    {
        if (node == null) {
            return;
        }
        printInorder(node.left);
        Console.Write(node.data + " ");
        printInorder(node.right);
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        int[] pre = new int[] { 10, 5, 1, 7, 40, 50 };
        int size = pre.Length;
        Node root = tree.constructTree(pre, size);
         
        tree.printInorder(root);
    }
}
 
// This code is contributed by Shrikant13


Javascript




<script>
 
// A O(n^2) javascript program for
// construction of BST from preorder traversal
 
// A binary tree node
 
 
class Node{
    // A constructor to create a new node
    constructor(data){
        this.data = data
        this.left = null
        this.right = null
    }
}
 
 
// constructTreeUtil.preIndex is a static variable of
// function constructTreeUtil
 
// Function to get the value of static variable
// constructTreeUtil.preIndex
function getPreIndex(){
    return constructTreeUtil.preIndex
}
 
// Function to increment the value of static variable
// constructTreeUtil.preIndex
 
 
function incrementPreIndex(){
    constructTreeUtil.preIndex += 1
}
 
// A recursive function to construct Full from pre[].
// preIndex is used to keep track of index in pre[[].
 
 
function constructTreeUtil(pre, low, high){
 
        // Base Case
    if(low > high)
        return null
 
    // The first node in preorder traversal is root. So take
    // the node at preIndex from pre[] and make it root,
    // and increment preIndex
    let root = new Node(pre[getPreIndex()])
    incrementPreIndex()
 
    // If the current subarray has only one element,
    // no need to recur
    if(low == high)
        return root
 
    let r_root = -1
 
    // Search for the first element greater than root
    for(let i=low;i<high+1;i++){
        if (pre[i] > root.data){
            r_root = i
            break
        }
    }
 
    // If no elements are greater than the current root,
    // all elements are left children
    // so assign root appropriately
    if(r_root == -1)
        r_root = getPreIndex() + (high - low)
 
    // Use the index of element found in preorder to divide
    // preorder array in two parts. Left subtree and right
    // subtree
    root.left = constructTreeUtil(pre, getPreIndex(), r_root-1)
 
    root.right = constructTreeUtil(pre, r_root, high)
 
    return root
}
 
// The main function to construct BST from given preorder
// traversal. This function mainly uses constructTreeUtil()
 
 
function constructTree(pre){
    let size = pre.length
    constructTreeUtil.preIndex = 0
    return constructTreeUtil(pre, 0, size-1)
}
 
function printInorder(root){
    if(root == null)
        return
    printInorder(root.left)
    document.write(root.data,' ')
    printInorder(root.right)
}
 
 
// Driver code
let pre = [10, 5, 1, 7, 40, 50]
 
let root = constructTree(pre)
 
printInorder(root)
 
// This code is contributed by shinjanpatra
 
</script>


Output

Inorder traversal of the constructed tree: 
1 5 7 10 40 50 

Time Complexity: O(N2)
Auxiliary Space: O(N)

Approach: To solve the problem follow the below idea:

 Using the recursion concept and iterating through the array of the given elements we can generate the BST

Follow the below steps to solve the problem:

  • Create a new Node for every value in the array
  • Create a BST using these new Nodes and insert them according to the rules of the BST
  • Print the inorder of the BST

Below is the implementation of the above approach:

C++




// C++ Program for the same approach
#include <bits/stdc++.h>
using namespace std;
 
/*Construct a BST from given pre-order traversal
for example if the given traversal is {10, 5, 1, 7, 40, 50},
then the output should be the root of the following tree.
     10
   /   \
  5     40
 /  \      \
1    7      50 */
 
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int data)
    {
        this->data = data;
        this->left = this->right = NULL;
    }
};
 
static Node* node;
 
// This will create the BST
Node* createNode(Node* node, int data)
{
    if (node == NULL)
        node = new Node(data);
 
    if (node->data > data)
        node->left = createNode(node->left, data);
    if (node->data < data)
        node->right = createNode(node->right, data);
 
    return node;
}
 
// A wrapper function of createNode
void create(int data) { node = createNode(node, data); }
// A function to print BST in inorder
void inorderRec(Node* root)
{
    if (root != NULL) {
        inorderRec(root->left);
        cout << root->data << " ";
        inorderRec(root->right);
    }
}
 
// Driver code
int main()
{
    vector<int> nodeData = { 10, 5, 1, 7, 40, 50 };
 
    for (int i = 0; i < nodeData.size(); i++) {
        create(nodeData[i]);
    }
    inorderRec(node);
}
 
// This code is contributed by shinjanpatra


Java




/*Construct a BST from given pre-order traversal
for example if the given traversal is {10, 5, 1, 7, 40, 50},
then the output should be the root of the following tree.
     10
   /   \
  5     40
 /  \      \
1    7      50 */
 
class Node {
    int data;
    Node left, right;
    Node(int data)
    {
        this.data = data;
        this.left = this.right = null;
    }
}
 
class CreateBSTFromPreorder {
    private static Node node;
 
    // This will create the BST
    public static Node createNode(Node node, int data)
    {
        if (node == null)
            node = new Node(data);
 
        if (node.data > data)
            node.left = createNode(node.left, data);
        if (node.data < data)
            node.right = createNode(node.right, data);
 
        return node;
    }
 
    // A wrapper function of createNode
    public static void create(int data)
    {
        node = createNode(node, data);
    }
    // A function to print BST in inorder
    public static void inorderRec(Node root)
    {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data);
              System.out.print(" ");
            inorderRec(root.right);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] nodeData = { 10, 5, 1, 7, 40, 50 };
 
        for (int i = 0; i < nodeData.length; i++) {
            create(nodeData[i]);
        }
        inorderRec(node);
    }
}


Python3




# Construct a BST from given pre-order traversal
# for example if the given traversal is {10, 5, 1, 7, 40, 50},
# then the output should be the root of the following tree.
#     10
#   /   \
#  5     40
# /  \      \
# 1    7      50
 
 
class Node:
    data = 0
    left = None
    right = None
 
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
class CreateBSTFromPreorder:
    node = None
    # This will create the BST
 
    @staticmethod
    def createNode(node,  data):
        if (node == None):
            node = Node(data)
        if (node.data > data):
            node.left = CreateBSTFromPreorder.createNode(node.left, data)
        if (node.data < data):
            node.right = CreateBSTFromPreorder.createNode(node.right, data)
        return node
 
    # A wrapper function of createNode
    @staticmethod
    def create(data):
        CreateBSTFromPreorder.node = CreateBSTFromPreorder.createNode(
            CreateBSTFromPreorder.node, data)
 
    # A function to print BST in inorder
    @staticmethod
    def inorderRec(root):
        if (root != None):
            CreateBSTFromPreorder.inorderRec(root.left)
            print(root.data)
            CreateBSTFromPreorder.inorderRec(root.right)
 
    # Driver Code
    @staticmethod
    def main(args):
        nodeData = [10, 5, 1, 7, 40, 50]
        i = 0
        while (i < len(nodeData)):
            CreateBSTFromPreorder.create(nodeData[i])
            i += 1
        CreateBSTFromPreorder.inorderRec(CreateBSTFromPreorder.node)
 
 
if __name__ == "__main__":
    CreateBSTFromPreorder.main([])
 
# This code is contributed by mukulsomukesh


C#




/*Construct a BST from given pre-order traversal
for example if the given traversal is {10, 5, 1, 7, 40, 50},
then the output should be the root of the following tree.
     10
   /   \
  5     40
 /  \      \
1    7      50 */
using System;
public class Node {
    public int data;
    public Node left, right;
    public Node(int data)
    {
        this.data = data;
        this.left = this.right = null;
    }
}
 
public class CreateBSTFromPreorder {
    private static Node node;
 
    // This will create the BST
    public static Node createNode(Node node, int data)
    {
        if (node == null)
            node = new Node(data);
 
        if (node.data > data)
            node.left = createNode(node.left, data);
        if (node.data < data)
            node.right = createNode(node.right, data);
 
        return node;
    }
 
    // A wrapper function of createNode
    public static void create(int data)
    {
        node = createNode(node, data);
    }
 
    // A function to print BST in inorder
    public static void inorderRec(Node root)
    {
        if (root != null) {
            inorderRec(root.left);
            Console.Write(root.data);
              Console.Write(" ");
            inorderRec(root.right);
        }
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] nodeData = { 10, 5, 1, 7, 40, 50 };
        for (int i = 0; i < nodeData.Length; i++) {
            create(nodeData[i]);
        }
        inorderRec(node);
    }
}
 
// This code is contributed by Rajput-Ji


Javascript




<script>
/*Construct a BST from given pre-order traversal
for example if the given traversal is {10, 5, 1, 7, 40, 50],
then the output should be the root of the following tree.
     10
   /   \
  5     40
 /  \      \
1    7      50 */
 
class Node {
    constructor(data) {
        this.data = data;
        this.left = this.right = null;
    }
}
 
var node;
 
    // This will create the BST
    function createNode(node , data) {
        if (node == null)
            node = new Node(data);
 
        if (node.data > data)
            node.left = createNode(node.left, data);
        if (node.data < data)
            node.right = createNode(node.right, data);
 
        return node;
    }
 
    // A wrapper function of createNode
    function create(data) {
        node = createNode(node, data);
    }
 
    // A function to print BST in inorder
    function inorderRec(root) {
        if (root != null) {
            inorderRec(root.left);
            document.write(root.data+"<br/>");
            inorderRec(root.right);
        }
    }
 
    // Driver Code
        var nodeData = [ 10, 5, 1, 7, 40, 50 ];
        for (i = 0; i < nodeData.length; i++)
        {
            create(nodeData[i]);
        }
        inorderRec(node);
 
 
// This code is contributed by Rajput-Ji
</script>


Output

1
5
7
10
40
50

Time Complexity: O(N2)
Auxiliary Space: O(N)

Efficient Approach: To solve the problem follow the below idea:

The trick is to set a range {min .. max} for every node. 

Follow the below steps to solve the problem:

  • Initialize the range as {INT_MIN .. INT_MAX}
  • The first node will definitely be in range, so create a root node. 
  • To construct the left subtree, set the range as {INT_MIN …root->data}. 
  • If a value is in the range {INT_MIN .. root->data}, the values are part of the left subtree. 
  • To construct the right subtree, set the range as {root->data..max .. INT_MAX}. 

Below is the implementation of the above approach:

C++




// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node {
public:
    int data;
    node* left;
    node* right;
};
 
// A utility function to create a node
node* newNode(int data)
{
    node* temp = new node();
 
    temp->data = data;
    temp->left = temp->right = NULL;
 
    return temp;
}
 
// A recursive function to construct
// BST from pre[]. preIndex is used
// to keep track of index in pre[].
node* constructTreeUtil(int pre[], int* preIndex, int key,
                        int min, int max, int size)
{
    // Base case
    if (*preIndex >= size)
        return NULL;
 
    node* root = NULL;
 
    // If current element of pre[] is in range, then
    // only it is part of current subtree
    if (key > min && key < max) {
        // Allocate memory for root of this
        // subtree and increment *preIndex
        root = newNode(key);
        *preIndex = *preIndex + 1;
 
        if (*preIndex < size) {
            // Construct the subtree under root
            // All nodes which are in range
            // {min .. key} will go in left
            // subtree, and first such node
            // will be root of left subtree.
            root->left = constructTreeUtil(pre, preIndex,
                                           pre[*preIndex],
                                           min, key, size);
        }
        if (*preIndex < size) {
            // All nodes which are in range
            // {key..max} will go in right
            // subtree, and first such node
            // will be root of right subtree.
            root->right = constructTreeUtil(pre, preIndex,
                                            pre[*preIndex],
                                            key, max, size);
        }
    }
 
    return root;
}
 
// The main function to construct BST
// from given preorder traversal.
// This function mainly uses constructTreeUtil()
node* constructTree(int pre[], int size)
{
    int preIndex = 0;
    return constructTreeUtil(pre, &preIndex, pre[0],
                             INT_MIN, INT_MAX, size);
}
 
// A utility function to print inorder
// traversal of a Binary Tree
void printInorder(node* node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    cout << node->data << " ";
    printInorder(node->right);
}
 
// Driver code
int main()
{
    int pre[] = { 10, 5, 1, 7, 40, 50 };
    int size = sizeof(pre) / sizeof(pre[0]);
 
    // Function call
    node* root = constructTree(pre, size);
 
    printInorder(root);
 
    return 0;
}
 
// This code is contributed by rathbhupendra


C




// C program for the above approach
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
// A utility function to create a node
struct node* newNode(int data)
{
    struct node* temp
        = (struct node*)malloc(sizeof(struct node));
 
    temp->data = data;
    temp->left = temp->right = NULL;
 
    return temp;
}
 
// A recursive function to construct BST from pre[].
// preIndex is used to keep track of index in pre[].
struct node* constructTreeUtil(int pre[], int* preIndex,
                               int key, int min, int max,
                               int size)
{
    // Base case
    if (*preIndex >= size)
        return NULL;
 
    struct node* root = NULL;
 
    // If current element of pre[] is in range, then
    // only it is part of current subtree
    if (key > min && key < max) {
        // Allocate memory for root of this subtree and
        // increment *preIndex
        root = newNode(key);
        *preIndex = *preIndex + 1;
 
        if (*preIndex < size) {
            // Construct the subtree under root
            // All nodes which are in range {min .. key}
            // will go in left subtree, and first such node
            // will be root of left subtree.
            root->left = constructTreeUtil(pre, preIndex,
                                           pre[*preIndex],
                                           min, key, size);
        }
        if (*preIndex < size) {
            // All nodes which are in range {key..max} will
            // go in right subtree, and first such node will
            // be root of right subtree.
            root->right = constructTreeUtil(pre, preIndex,
                                            pre[*preIndex],
                                            key, max, size);
        }
    }
 
    return root;
}
 
// The main function to construct BST from given preorder
// traversal. This function mainly uses constructTreeUtil()
struct node* constructTree(int pre[], int size)
{
    int preIndex = 0;
    return constructTreeUtil(pre, &preIndex, pre[0],
                             INT_MIN, INT_MAX, size);
}
 
// A utility function to print inorder traversal of a Binary
// Tree
void printInorder(struct node* node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    printf("%d ", node->data);
    printInorder(node->right);
}
 
// Driver code
int main()
{
    int pre[] = { 10, 5, 1, 7, 40, 50 };
    int size = sizeof(pre) / sizeof(pre[0]);
 
    // function call
    struct node* root = constructTree(pre, size);
 
     
    printInorder(root);
 
    return 0;
}


Java




// Java program to construct BST from given preorder
// traversal
 
// A binary tree node
class Node {
 
    int data;
    Node left, right;
 
    Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
class Index {
 
    int index = 0;
}
 
class BinaryTree {
 
    Index index = new Index();
 
    // A recursive function to construct BST from pre[].
    // preIndex is used to keep track of index in pre[].
    Node constructTreeUtil(int pre[], Index preIndex,
                           int key, int min, int max,
                           int size)
    {
 
        // Base case
        if (preIndex.index >= size) {
            return null;
        }
 
        Node root = null;
 
        // If current element of pre[] is in range, then
        // only it is part of current subtree
        if (key > min && key < max) {
 
            // Allocate memory for root of this
            // subtree and increment *preIndex
            root = new Node(key);
            preIndex.index = preIndex.index + 1;
 
            if (preIndex.index < size) {
 
                // Construct the subtree under root
                // All nodes which are in range {min .. key}
                // will go in left subtree, and first such
                // node will be root of left subtree.
                root.left = constructTreeUtil(
                    pre, preIndex, pre[preIndex.index], min,
                    key, size);
            }
            if (preIndex.index < size) {
                // All nodes which are in range {key..max}
                // will go in right subtree, and first such
                // node will be root of right subtree.
                root.right = constructTreeUtil(
                    pre, preIndex, pre[preIndex.index], key,
                    max, size);
            }
        }
 
        return root;
    }
 
    // The main function to construct BST from given
    // preorder traversal. This function mainly uses
    // constructTreeUtil()
    Node constructTree(int pre[], int size)
    {
        int preIndex = 0;
        return constructTreeUtil(pre, index, pre[0],
                                 Integer.MIN_VALUE,
                                 Integer.MAX_VALUE, size);
    }
 
    // A utility function to print inorder traversal of a
    // Binary Tree
    void printInorder(Node node)
    {
        if (node == null) {
            return;
        }
        printInorder(node.left);
        System.out.print(node.data + " ");
        printInorder(node.right);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        int pre[] = new int[] { 10, 5, 1, 7, 40, 50 };
        int size = pre.length;
 
        // Function call
        Node root = tree.constructTree(pre, size);
         
        tree.printInorder(root);
    }
}
 
// This code has been contributed by Mayank Jaiswal


Python3




# Python3 program for the above approach
 
INT_MIN = -float("inf")
INT_MAX = float("inf")
 
# A Binary tree node
 
 
class Node:
 
    # Constructor to created a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Methods to get and set the value of static variable
# constructTreeUtil.preIndex for function construcTreeUtil()
 
 
def getPreIndex():
    return constructTreeUtil.preIndex
 
 
def incrementPreIndex():
    constructTreeUtil.preIndex += 1
 
# A recursive function to construct BST from pre[].
# preIndex is used to keep track of index in pre[]
 
 
def constructTreeUtil(pre, key, mini, maxi, size):
 
    # Base Case
    if(getPreIndex() >= size):
        return None
 
    root = None
 
    # If current element of pre[] is in range, then
    # only it is part of current subtree
    if(key > mini and key < maxi):
 
        # Allocate memory for root of this subtree
        # and increment constructTreeUtil.preIndex
        root = Node(key)
        incrementPreIndex()
 
        if(getPreIndex() < size):
 
            # Construct the subtree under root
            # All nodes which are in range {min.. key} will
            # go in left subtree, and first such node will
            # be root of left subtree
            root.left = constructTreeUtil(pre,
                                          pre[getPreIndex()],
                                          mini, key, size)
        if(getPreIndex() < size):
 
            # All nodes which are in range{key..max} will
            # go to right subtree, and first such node will
            # be root of right subtree
            root.right = constructTreeUtil(pre,
                                           pre[getPreIndex()],
                                           key, maxi, size)
 
    return root
 
# This is the main function to construct BST from given
# preorder traversal. This function mainly uses
# constructTreeUtil()
 
 
def constructTree(pre):
    constructTreeUtil.preIndex = 0
    size = len(pre)
    return constructTreeUtil(pre, pre[0], INT_MIN, INT_MAX, size)
 
 
# A utility function to print inorder traversal of Binary Tree
def printInorder(node):
 
    if node is None:
        return
    printInorder(node.left)
    print(node.data, end=" ")
    printInorder(node.right)
 
 
# Driver code
pre = [10, 5, 1, 7, 40, 50]
 
# Function call
root = constructTree(pre)
 
 
printInorder(root)
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)


C#




// C# program to construct BST from given preorder traversal
using System;
 
// A binary tree node
public class Node {
 
    public int data;
    public Node left, right;
 
    public Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
public class Index {
    public int index = 0;
}
 
public class BinaryTree {
 
    public Index index = new Index();
 
    // A recursive function to construct BST from pre[].
    // preIndex is used to keep track of index in pre[].
    public virtual Node constructTreeUtil(int[] pre,
                                          Index preIndex,
                                          int key, int min,
                                          int max, int size)
    {
 
        // Base case
        if (preIndex.index >= size) {
            return null;
        }
 
        Node root = null;
 
        // If current element of pre[] is in range, then
        // only it is part of current subtree
        if (key > min && key < max) {
 
            // Allocate memory for root of this subtree
            // and increment *preIndex
            root = new Node(key);
            preIndex.index = preIndex.index + 1;
 
            if (preIndex.index < size) {
 
                // Construct the subtree under root
                // All nodes which are in range
                // {min .. key} will go in left
                // subtree, and first such node will
                // be root of left subtree.
                root.left = constructTreeUtil(
                    pre, preIndex, pre[preIndex.index], min,
                    key, size);
            }
            if (preIndex.index < size) {
                // All nodes which are in range
                // {key..max} will go in right
                // subtree, and first such node
                // will be root of right subtree.
                root.right = constructTreeUtil(
                    pre, preIndex, pre[preIndex.index], key,
                    max, size);
            }
        }
 
        return root;
    }
 
    // The main function to construct BST from given
    // preorder traversal. This function mainly uses
    // constructTreeUtil()
    public virtual Node constructTree(int[] pre, int size)
    {
 
        return constructTreeUtil(pre, index, pre[0],
                                 int.MinValue, int.MaxValue,
                                 size);
    }
 
    // A utility function to print inorder traversal of a
    // Binary Tree
    public virtual void printInorder(Node node)
    {
        if (node == null) {
            return;
        }
        printInorder(node.left);
        Console.Write(node.data + " ");
        printInorder(node.right);
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        int[] pre = new int[] { 10, 5, 1, 7, 40, 50 };
        int size = pre.Length;
 
        // Function call
        Node root = tree.constructTree(pre, size);
         
        tree.printInorder(root);
    }
}
 
// This code is contributed by Shrikant13


Javascript




<script>
// javascript program to construct BST from given preorder
// traversal
 
// A binary tree node
class Node {
 
    constructor(d) {
        this.data = d;
        this.left = this.right = null;
    }
}
 
class Index {
    constructor(){
    this.index = 0;
    }
}
 
index = new Index();
 
    // A recursive function to construct BST from pre.
    // preIndex is used to keep track of index in pre.
    function constructTreeUtil(pre,  preIndex , key , min , max , size) {
 
        // Base case
        if (preIndex.index >= size) {
            return null;
        }
 
var root = null;
 
        // If current element of pre is in range, then
        // only it is part of current subtree
        if (key > min && key < max) {
 
            // Allocate memory for root of this
            // subtree and increment *preIndex
            root = new Node(key);
            preIndex.index = preIndex.index + 1;
 
            if (preIndex.index < size) {
 
                // Construct the subtree under root
                // All nodes which are in range {min .. key}
                // will go in left subtree, and first such
                // node will be root of left subtree.
                root.left = constructTreeUtil(pre, preIndex,
                pre[preIndex.index], min, key, size);
            }
            if (preIndex.index < size)
            {
             
                // All nodes which are in range {key..max}
                // will go in right subtree, and first such
                // node will be root of right subtree.
                root.right = constructTreeUtil(pre, preIndex,
                pre[preIndex.index], key, max, size);
            }
        }
 
        return root;
    }
 
    // The main function to construct BST from given
    // preorder traversal. This function mainly uses
    // constructTreeUtil()
    function constructTree(pre , size) {
        var preIndex = 0;
        return constructTreeUtil(pre, index, pre[0],
        Number.MIN_VALUE, Number.MAX_VALUE, size);
    }
 
    // A utility function to print inorder traversal of a
    // Binary Tree
    function printInorder(node) {
        if (node == null) {
            return;
        }
        printInorder(node.left);
        document.write(node.data + " ");
        printInorder(node.right);
    }
 
    // Driver code
        var pre =[ 10, 5, 1, 7, 40, 50 ];
        var size = pre.length;
 
        // Function call
        var root = constructTree(pre, size);
        document.write("Inorder traversal of the constructed tree is <br/>");
        printInorder(root);
 
// This code is contributed by Rajput-Ji
</script>


Output

Inorder traversal of the constructed tree: 
1 5 7 10 40 50 

Time Complexity: O(N)
Auxiliary Space: O(N)



Previous Article
Next Article

Similar Reads

Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree
Given two arrays that represent Preorder traversals of a full binary tree and its mirror tree, we need to write a program to construct the binary tree using these two Preorder traversals.A Full Binary Tree is a binary tree where every node has either 0 or 2 children. Note: It is not possible to construct a general binary tree using these two traver
12 min read
Construct BST from given preorder traversal using Stack
Given preorder traversal of a binary search tree, construct the BST.For example, if the given traversal is {10, 5, 1, 7, 40, 50}, then the output should be root of following tree. 10 / \ 5 40 / \ \ 1 7 50 We have discussed O(n^2) and O(n) recursive solutions in the previous post. Following is a stack based iterative solution that works in O(n) time
13 min read
Construct BST from given preorder traversal using Sorting
Given preorder traversal of a binary search tree, construct the BST.For example, if the given traversal is {10, 5, 1, 7, 40, 50}, then the output should be root of following tree. 10 / \ 5 40 / \ \ 1 7 50 We have discussed methods to construct binary search tree in previous posts.Here is another method to construct binary search tree when given pre
10 min read
Find postorder traversal of BST from preorder traversal
Given an array representing preorder traversal of BST, print its postorder traversal. Examples: Input : 40 30 35 80 100 Output : 35 30 100 80 40 Input : 40 30 32 35 80 90 100 120 Output : 35 32 30 120 100 90 80 40 Prerequisite: Construct BST from given preorder traversal Simple Approach: A simple solution is to first construct BST from a given preo
9 min read
Find Leftmost and Rightmost node of BST from its given preorder traversal
Given a preorder sequence of the binary search tree of N nodes. The task is to find its leftmost and rightmost nodes. Examples: Input : N = 5, preorder[]={ 3, 2, 1, 5, 4 } Output : Leftmost = 1, Rightmost = 5 The BST constructed from this preorder sequence would be: 3 / \ 2 5 / / 1 4 Leftmost Node of this tree is equal to 1 Rightmost Node of this t
5 min read
Construct a special tree from given preorder traversal
Given an array 'pre[]' that represents Preorder traversal of a special binary tree where every node has either 0 or 2 children. One more array 'preLN[]' is given which has only two possible values 'L' and 'N'. The value 'L' in 'preLN[]' indicates that the corresponding node in Binary Tree is a leaf node and value 'N' indicates that the correspondin
15+ min read
Number of elements smaller than root using preorder traversal of a BST
Given a preorder traversal of a BST. The task is to find the number of elements less than root. Examples: Input: preorder[] = {3, 2, 1, 0, 5, 4, 6} Output: 3 Input: preorder[] = {5, 4, 3, 2, 1} Output: 4 For a binary search tree, a preorder traversal is of the form: root, { elements in left subtree of root }, { elements in right subtree of root } S
9 min read
Construct BST from its given level order traversal | Set-2
Construct the BST (Binary Search Tree) from its given level order traversal. Examples: Input : {7, 4, 12, 3, 6, 8, 1, 5, 10} Output : BST: 7 / \ 4 12 / \ / 3 6 8 / / \ 1 5 10Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. Approach : The idea is to make a struct element NodeDetails which contains a pointer to the
15+ min read
Construct a Perfect Binary Tree from Preorder Traversal
Given an array pre[], representing the Preorder traversal of a Perfect Binary Tree consisting of N nodes, the task is to construct a Perfect Binary Tree from the given Preorder Traversal and return the root of the tree. Examples: Input: pre[] = {1, 2, 4, 5, 3, 6, 7}Output: 1 / \ / \ 2 3 / \ / \ / \ / \ 4 5 6 7 Input: pre[] = {1, 2, 3}Output: 1 / \
11 min read
Construct the full k-ary tree from its preorder traversal
Given an array that contains the preorder traversal of the full k-ary tree, construct the full k-ary tree and print its postorder traversal. A full k-ary tree is a tree where each node has either 0 or k children. Examples: Input : preorder[] = {1, 2, 5, 6, 7, 3, 8, 9, 10, 4} k = 3 Output : Postorder traversal of constructed full k-ary tree is: 5 6
10 min read
Article Tags :
Practice Tags :