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 preorder traversal.
We know that the inorder traversal of the BST gives the element in non-decreasing manner. Hence we can sort the given preorder traversal to obtain the inorder traversal of the binary search tree.
We have already learnt the method to construct tree when given preorder and inorder traversals in this post. We will now use the same method to construct the BST.
C++
#include <bits/stdc++.h>using namespace std;// A BST node has data, pointer to left // child and pointer to right childstruct Node { int data; Node *left, *right;};// A utility function to create new nodeNode* getNode(int data){ Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp;}/* Recursive function to construct BSTInorder traversal in[] and Preorder traversalpre[]. Initial values of inStart and inEnd should be0 and n -1.*/Node* buildBTRec(int in[], int pre[], int inStart, int inEnd, unordered_map<int,int>& m){ static int preIdx = 0; if (inStart > inEnd) return NULL; // Pick current node from Preorder traversal // using preIndex and increment preIndex int curr = pre[preIdx]; ++preIdx; Node* temp = getNode(curr); // If this node has no children then return if (inStart == inEnd) return temp; // Else find the index of this node in // inorder traversal int idx = m[curr]; // Using this index construct left and right subtrees temp->left = buildBTRec(in, pre, inStart, idx - 1, m); temp->right = buildBTRec(in, pre, idx + 1, inEnd, m); return temp;}// This function mainly creates a map to store // the indices of all items so we can quickly // access them later.Node* buildBST(int pre[], int n){ // Copy pre[] to in[] and sort it int in[n]; for (int i = 0; i < n; i++) in[i] = pre[i]; sort(in, in + n); unordered_map<int,int> m; for(int i=0;i<n;i++) { m[in[i]] = i; } return buildBTRec(in, pre, 0, n-1,m); }// Inorder Traversal of treevoid inorderTraversal(Node* node){ if(node==NULL) return ; inorderTraversal(node->left); cout << node->data << " "; inorderTraversal(node->right);}// Driver Programint main(){ int pre[] = { 100, 20, 10, 30, 200, 150, 300 }; int n = sizeof(pre) / sizeof(pre[0]); Node* root = buildBST(pre, n); // Let's test the built tree by printing its // Inorder traversal cout << "Inorder traversal of the tree is \n"; inorderTraversal(root); return 0;} |
Python3
# A BST node has data, pointer to left# child and pointer to right childclass Node: def __init__(self, x): self.data = x self.left = None self.right = None# /* Recursive function to construct BST# Inorder traversal in[] and Preorder traversal# pre[]. Initial values of inStart and inEnd should be# 0 and n -1.*/def buildBTRec(inn, pre, inStart, inEnd): global m, preIdx if (inStart > inEnd): return None # Pick current node from Preorder traversal # using preIndex and increment preIndex curr = pre[preIdx] preIdx += 1 temp = Node(curr) # If this node has no children then return if (inStart == inEnd): return temp # Else find the index of this node in # inorder traversal idx = m[curr] # Using this index construct left and right subtrees temp.left = buildBTRec(inn, pre, inStart, idx - 1) temp.right = buildBTRec(inn, pre, idx + 1, inEnd) return temp# This function mainly creates a map to store# the indices of all items so we can quickly# access them later.def buildBST(pre, n): global m # Copy pre[] to in[] and sort it inn=[0 for i in range(n)] for i in range(n): inn[i] = pre[i] inn = sorted(inn) for i in range(n): m[inn[i]] = i return buildBTRec(inn, pre, 0, n - 1)def inorderTraversal(root): if (root == None): return inorderTraversal(root.left) print(root.data, end = " ") inorderTraversal(root.right)# Driver Programif __name__ == '__main__': m,preIdx = {}, 0 pre = [100, 20, 10, 30, 200, 150, 300] n = len(pre) root = buildBST(pre, n) # Let's test the built tree by printing its # Inorder traversal print("Inorder traversal of the tree is") inorderTraversal(root)# This code is contributed by mohit kumar 29 |
Java
import java.util.*;class Node { int data; Node left, right; Node(int d) { data = d; left = right = null; }} public class Main { static int preIdx = 0; static HashMap<Integer, Integer> m = new HashMap<Integer, Integer>(); // Recursive function to construct BST // Inorder traversal in[] and Preorder traversal pre[] // Initial values of inStart and inEnd should be 0 and n -1. public static Node buildBTRec(int[] inn, int[] pre, int inStart, int inEnd) { if (inStart > inEnd) { return null; } // Pick current node from Preorder traversal // using preIndex and increment preIndex int curr = pre[preIdx]; preIdx++; Node temp = new Node(curr); // If this node has no children then return if (inStart == inEnd) { return temp; } // Else find the index of this node in // inorder traversal int idx = m.get(curr); // Using this index construct left and right subtrees temp.left = buildBTRec(inn, pre, inStart, idx - 1); temp.right = buildBTRec(inn, pre, idx + 1, inEnd); return temp; } // This function mainly creates a map to store // the indices of all items so we can quickly // access them later. public static Node buildBST(int[] pre, int n) { int[] inn = new int[n]; for (int i = 0; i < n; i++) { inn[i] = pre[i]; } Arrays.sort(inn); for (int i = 0; i < n; i++) { m.put(inn[i], i); } return buildBTRec(inn, pre, 0, n - 1); } public static void inorderTraversal(Node root) { if (root == null) { return; } inorderTraversal(root.left); System.out.print(root.data + " "); inorderTraversal(root.right); } // Driver Program public static void main(String[] args) { int[] pre = {100, 20, 10, 30, 200, 150, 300}; int n = pre.length; Node root = buildBST(pre, n); // Let's test the built tree by printing its // Inorder traversal System.out.println("Inorder traversal of the tree is:"); inorderTraversal(root); }} |
C#
// C# Program for the above approachusing System;using System.Collections;using System.Collections.Generic;// class containing left and right// child of current node and key valuepublic class Node{ public int data; public Node left, right; public Node(int item){ data = item; left = right = null; }}class GFG{ public static int preIdx = 0; public static Dictionary<int, int> m = new Dictionary<int, int>(); /* Recursive function to construct BST Inorder traversal in[] and Preorder traversal pre[]. Initial values of inStart and inEnd should be 0 and n -1.*/ public static Node buildBTRec(int[] In, int[] pre, int inStart, int inEnd){ if(inStart > inEnd) return null; // Pick current node from Preorder traversal // using preIndex and increment preIndex int curr = pre[preIdx]; preIdx += 1; Node temp = new Node(curr); // if this node has no children then return if(inStart == inEnd) return temp; // else find the index of this node in // inorder traversal int idx = m[curr]; // using this index construct left and right subtrees temp.left = buildBTRec(In, pre, inStart, idx-1); temp.right = buildBTRec(In, pre, idx+1, inEnd); return temp; } // This function mainly creates a map to store // the indices of all items so we can quickly // access them later. public static Node buildBST(int[] pre, int n){ // copy pre[] to in[] and sort it int[] In = new int[n]; for(int i = 0; i<n; i++){ In[i] = pre[i]; } Array.Sort(In); for(int i = 0; i<n; i++){ m[In[i]] = i; } return buildBTRec(In, pre, 0, n-1); } public static void inorderTraversal(Node root){ if(root == null) return; inorderTraversal(root.left); Console.Write(root.data + " "); inorderTraversal(root.right); } public static void Main(string[] args){ int[] pre = {100, 20, 10, 30, 200, 150, 300}; int n = pre.Length; Node root = buildBST(pre, n); // Let's test the build tree by printing its // Inorder traversal Console.WriteLine("Inorder Traversal of the tree is : "); inorderTraversal(root); }}// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Javascript
<script>// A BST node has data, pointer to left// child and pointer to right childclass Node{ constructor(data) { this.data = data; this.left = this.right = null; }}/* Recursive function to construct BSTInorder traversal in[] and Preorder traversalpre[]. Initial values of inStart and inEnd should be0 and n -1.*/function buildBTRec(In, pre, inStart, inEnd){ if (inStart > inEnd) return null; // Pick current node from Preorder traversal // using preIndex and increment preIndex let curr = pre[preIdx]; ++preIdx; let temp = new Node(curr); // If this node has no children then return if (inStart == inEnd) return temp; // Else find the index of this node in // inorder traversal let idx = m.get(curr); // Using this index construct left and right subtrees temp.left = buildBTRec(In, pre, inStart, idx - 1); temp.right = buildBTRec(In, pre, idx + 1, inEnd); return temp;}// This function mainly creates a map to store// the indices of all items so we can quickly// access them later.function buildBST(pre, n){ // Copy pre[] to in[] and sort it let In = new Array(n); for(let i = 0; i < n; i++) In[i] = pre[i]; In.sort(function(a, b){return a - b;}); for(let i = 0; i < n; i++) m.set(In[i], i); return buildBTRec(In, pre, 0, n - 1)}function inorderTraversal(root){ if (root == null) return; inorderTraversal(root.left); document.write(root.data + " "); inorderTraversal(root.right);}// Driver codelet m = new Map();let preIdx = 0;let pre = [ 100, 20, 10, 30, 200, 150, 300 ];let n = pre.length;let root = buildBST(pre, n);// Let's test the built tree by printing its// Inorder traversaldocument.write("Inorder traversal of the tree is <br>");inorderTraversal(root);// This code is contributed by patel2127</script> |
Output:
Inorder traversal of the tree is 10 20 30 100 150 200 300
Time Complexity: Sorting takes O(nlogn) time for sorting and constructing using preorder and inorder traversals takes linear time. Hence overall time complexity of the above solution is O(nlogn).
“The time complexity of the buildBST function is O(n log n), where n is the number of nodes in the binary search tree. This is because the function sorts the input array of preorder traversal and this sorting takes O(n log n) time. The buildBTRec function is called recursively for each node in the tree, and each node is processed once, so the total time complexity of the buildBTRec function is O(n). Therefore, the time complexity of the entire algorithm is O(n log n).”
Auxiliary Space: O(n).
“The space complexity of the algorithm is O(n) because the m HashMap is used to store the indices of all the items, and it requires O(n) space. Additionally, the buildBTRec function is called recursively for each node in the tree, and the maximum depth of the recursive call stack is O(n), so the space used by the call stack is also O(n). Therefore, the total space complexity of the algorithm is O(n).”
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
