Given a distinct sequence of keys which represents preorder traversal of a binary search tree (BST), construct the tree from the postorder sequence.
For example, below BST should be constructed for preorder traversal { 15, 10, 8, 12, 20, 16, 25 }
For a given preorder sequence, we can easily build a BST by recursively repeating the following steps for all keys in it.
- Construct the root node of BST which would be the first key in the preorder sequence.
- Find index i of the first key in the preorder sequence which is greater than the root node.
- Recur for the left sub-tree with keys in the preorder sequence that appears before the i’th index (excluding first index).
- Recur for the right sub-tree with keys in the preorder sequence that appears after the i’th index (including i’th index).
To make context more clear, let’s consider the preorder traversal {15, 10, 8, 12, 20, 16, 25}
- The first item in the preorder sequence 15 becomes the root node.
- Since 20 is the first key in the preorder sequence which greater than the root node, left sub-tree consists of keys {10, 8, 12} and right sub-tree consists of keys {20, 16, 25}.
- To construct the complete BST, recursively repeat the above steps for preorder sequence {10, 8, 12} and {20, 16, 25}.
This is demonstrated below in C –
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include <stdio.h> #include <stdlib.h> // Data structure to store a Binary Tree node struct Node { int key; struct Node *left, *right; }; // Function to create a new binary tree node having given key struct Node* newNode(int key) { struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->key = key; node->left = node->right = NULL; return node; } // Recursive function to perform inorder traversal of a binary tree void inorder(struct Node* root) { if (root == NULL) return; inorder(root->left); printf("%d ", root->key); inorder(root->right); } // Recursive function to build a BST from a preorder sequence struct Node* constructBST(int preorder[], int start, int end) { // base case if (start > end) return NULL; // Construct the root node of the sub-tree formed by keys of the // preorder sequence in range [start, end] struct Node *node = newNode(preorder[start]); // search the index of first element in current range of preorder // sequence which is larger than the value of root node int i; for (i = start; i <= end; i++) { if (preorder[i] > node->key) break; } // recursively construct the left sub-tree node->left = constructBST(preorder, start + 1, i - 1); // recursively construct the right sub-tree node->right = constructBST(preorder, i, end); // return current node return node; } // main function int main(void) { /* Construct below BST 15 / \ / \ 10 20 / \ / \ / \ / \ 8 12 16 25 */ int preorder[] = { 15, 10, 8, 12, 20, 16, 25 }; int n = sizeof(preorder)/sizeof(preorder[0]); // construct the BST struct Node* root = constructBST(preorder, 0, n - 1); // print the BST printf("Inorder Traversal of BST is : "); // inorder on the BST always returns a sorted sequence inorder(root); return 0; } |
Output:
Inorder Traversal of BST is : 8 10 12 15 16 20 25
The time complexity of above solution is O(n2) and takes O(n) extra space for the call stack. We can reduce the time complexity to O(n) by following a different approach that doesn’t involve searching for index which separates the keys of left and right sub-tree in preorder sequence.
We know that in a BST, each node has key which is greater than all keys present in its left sub-tree, and less than the keys present in the right sub-tree. The idea to pass the information regarding the valid range of keys for current root node and its children in the recursion itself.
We start by setting the range as [INT_MIN, INT_MAX] for the root node. This means that the root node and any of its children can have keys in the ranging between INT_MIN and INT_MAX. Like previous approach, we construct the root node of BST from the first item in the preorder sequence. Suppose the root node has value x, we recur for right sub-tree with range (x, INT_MAX) and recur for left sub-tree with range [INT_MIN, x). To construct the complete BST, we recursively set the range for each recursive call and simply return if next element of preorder traversal is out of the valid range.
Here’s a C++ program that demonstrates it:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
#include <iostream> #include <vector> #include <climits> using namespace std; // Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Function to create a new binary tree node having given key Node* newNode(int key) { Node* node = new Node; node->data = key; node->left = node->right = nullptr; return node; } // Function to print the inorder traversal of a binary tree void inorder(Node* root) { if (root == nullptr) return; inorder(root->left); cout << root->data << ' '; inorder(root->right); } // Recursive function to build a BST from a preorder sequence Node* buildTree(vector<int> const &preorder, int& pIndex, int min, int max) { // Base case if (pIndex == preorder.size()) return nullptr; // Return if next element of preorder traversal is not in the valid range int val = preorder[pIndex]; if (val < min || val > max) return nullptr; // Construct the root node and increment pIndex Node* root = newNode(val); pIndex++; // Since all elements in the left sub-tree of a BST must be less // than the value of root node, set range as [min, val-1] and recur root->left = buildTree(preorder, pIndex, min, val-1); // Since all elements in the right sub-tree of a BST must be greater // than the value of root node, set range as [val+1..max] and recur root->right = buildTree(preorder, pIndex, val+1, max); return root; } // Build a BST from a preorder sequence Node* buildTree(vector<int> const &preorder) { // start from the root node (first element in preorder sequence) int pIndex = 0; // set range of the root node as [INT_MIN, INT_MAX] and recur return buildTree(preorder, pIndex, INT_MIN, INT_MAX); } // main function int main() { /* Construct below BST 15 / \ / \ 10 20 / \ / \ / \ / \ 8 12 16 25 */ // preorder traversal of BST vector<int> preorder = { 15, 10, 8, 12, 20, 16, 25 }; // construct the BST Node* root = buildTree(preorder); // print the BST cout << "Inorder Traversal of BST is : "; // inorder on the BST always returns a sorted sequence inorder(root); return 0; } |
Output:
Inorder Traversal of BST is : 8 10 12 15 16 20 25
(1 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply