Approach 1
Pre-order traversal follows the order root->left->right. Given that is is a BST, we have to leverage the property of a BST that the left subtree will have values less than that of the node and the right subtree will have values greater than the value of that node. Using this information, let’s try to build a tree for the given preorder traversal.
Preorder traversal: [8,5,1,7,10,12]
Since the order is root -> left subtree -> right subtree, 8 has to be the root.
Then, 5 is a potential candidate for the left child of 8. 5 < 8 ? yes. 5 being the left child of 8 doesn't violate any condition of BST so we'll set 5 to be the left child of 8.
Now, 1 is a potential candidate for the left child 5. 1 < 5 ? yes. So 1 will be left child of 5.
Tree till now:
8
/
5
/
1
Now, 7 is a potential candidate for the left child of 1. 7 < 1 ? no. So it can't be left child of 1.
Now, 7 is a potential candidate for the right child of 1. 7 < 5 (since 7 still lies in left subtree of 5) ? no. So it can't be right child of 1.
Now, 7 is a potential candidate for the right child of 5. 5 < 7 < 8 ? yes. Note that we know for sure that 7 > 5 because we rejected the previous case (7 being the right child of 1) on that basis only. We'll see later why this is useful. 7 will be the right child of 5.
Now, 10 is a potential candidate for the left child of 7. 10 < 7 ? no. So it can't be left child of 7.
Now, 10 is a potential candidate for the right child of 7. 10 < 8 ? no (since 7 still lies in the left subtree of 8). So it can't be right child of 7.
Tree till now:
8
/
5
/ \
1 7
Now, 10 is a potential candidate for the right child of 8. In the last statement, we already said that 10 is not less than 8 or 10 is greater than 8 (nodes are given to be distinct). So 10 will be right child of 8.
Now, 12 < 10 ? no. So 12 will be the right child of 10.
Final BST:
8
/ \
5 10
/ \ \
1 7 12
The below code leverages the lower and upper bound property of a BST for each node as explained above:
TreeNode* bstFromPreorder(vector<int>& preorder) {
int idx=0;
return helper(preorder, idx, INT_MIN, INT_MAX);
}
TreeNode* helper (vector<int>& preorder, int& idx, int lower, int upper) {
if (idx>=preorder.size() || preorder[idx]<lower || preorder[idx]>upper)
return NULL;
TreeNode *node = new TreeNode(preorder[idx++]);
node->left = helper(preorder, idx, lower, node->val);
node->right = helper(preorder, idx, node->val, upper);
return node;
}
Time complexity: O(n)
Approach 2: Similar but intriguing
Go through the example above once again and note that we don’t really need to check the lower bounds. I mentioned above in the example “We’ll see later why this is useful”. We can eliminate the need of lower bound in our function as well as checking against upper bounds is enough for us!
// we do not need the lower bounds
TreeNode* bstFromPreorder(vector<int>& preorder) {
int idx=0;
return helper(preorder, idx, INT_MAX);
}
TreeNode* helper (vector<int>& preorder, int& idx, int bound) {
if (idx>=preorder.size() || preorder[idx]>bound)
return NULL;
TreeNode *node = new TreeNode(preorder[idx++]);
node->left = helper(preorder, idx, node->val);
node->right = helper(preorder, idx, bound);
return node;
}
Approach 3: Iterative
Similar idea as explained above:
- First item in preorder list is the root to be considered.
- For next item in preorder list, there are 2 cases to consider: 1. If value is less than last item in stack, it is the left child of last item. 2. Else until the value is greater than last item in stack, pop from stack. The last popped item will be the parent and the item will be the right child of the parent.
- Push the item to stack
// iterative solution
TreeNode* bstFromPreorder(vector<int>& preorder) {
int idx=0;
TreeNode* root = new TreeNode(preorder[idx++]);
stack<TreeNode*> st;
st.push(root);
while (idx<preorder.size()) {
TreeNode* temp = st.top();
if (preorder[idx]<temp->val) {
temp->left = new TreeNode(preorder[idx++]);
st.push(temp->left);
} else {
while (!st.empty() && st.top()->val < preorder[idx]) {
temp = st.top();
st.pop();
}
temp->right = new TreeNode(preorder[idx++]);
st.push(temp->right);
}
}
return root;
}