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
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply