Jan 16, 2021
Demystifying Various BST Problems on LeetCode
Having an understanding of various variations of Trees problems and solving them intuitively might be intriguing in the beginning. If you are one of the them, starting to practice leetcode recently, hold on and take a deep breath. I have curated a list of leetcode problems on BST and their thinking process to get them solved easily and optimally. Solving a problem is not a big deal but the entire thinking and approach process behind the solution is what will make the leetcode journey easy and you would be able to gain confidence through practice. LeetCode Discuss platform would really help you getting the insight of the problem but getting trap in understanding various solutions in leetcode forum might kill lot of time . Here are the steps to get the basic understanding clear about the problem and proceed henceforth.
Trees problem are mostly solved using recursion. Before attempting any trees problem, try to collate all the given hints in the question and use in the solution as much as possible to arrive at optimal solution.
Given above the leetcode question to find the Inorder successor of a given node in BST. While there are many solutions posted out on internet for this problem, let me brief out the pros and cons of each solution.
i)Hints: Its a BST, Hence we should utilise BST property and most common BST property is inorder traversal of BST gives us sorted array.
ii) Time and Space Complexity Analysis: Using any one of the traversal, would take O(N) time complexity worst case in case of recursive solutions,O(N) time complexity,O(N) space complexity in case of iterative solutions(stack based) or O(N) time complexity in case of Threaded/Morris traversal.
iii) Hence, which one to choose to solve the above problem? Since we know its a BST, we need to come up with O(logn) time complexity to solve this problem. If above given question would have been for a binary tree, then we would have gone through O(N) solution using one of the traversals logic and tweaking the traversal to get the solution.
There are three ways to solve such tree problems :
i) Based on use cases which are possible for the given question. Let’s see an example: Whats an inorder successor for a given node in a tree? The node which appears just after the given node in inorder traversal output which is leftNode -> root -> RightNode in this order. Hence, total three cases are possible:
- GivenNode: leftNode. O/P: root
- GivenNode: root.O/P: rightNode
- GivenNode:rightNode.O/P: nullptr(in c++)
Hence, there is basically two cases since 3rd case is straighforward, if the given node is the rightmost node of the tree, output will be nullptr. Coming to other two cases: i)when the GivenNode=root, inorder successor will be in right subtree which is right child or left most node of the right child.
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p){
TreeNode* inorder = nullptr; if(p->right!=nullptr){
inorder = p->right;
while(inorder->left!=nullptr){
inorder = inorder->left;
}
}return inorder;
}
In above scenario, we iterated the tree in a specific fashion according to our use case . We can visualise this use case where the output node is below the given node. Hence, O(total height — height of node p) traversal is needed to get the result.Time Complexity = O(height of given node p). ii)when the GivenNode: leftNode, inorder successor will lie above in the tree.Hence, we need a way to track back the ancestor path. How do we track back the ancestor path, using one of the standard traversals way i.e. inorder traversal.While traversing using either(recursion,iterative(stack),morris) make sure to store prev element. Hence, when prev element=givenNode, currentNode will be inorderSuccessor of the givenNode.Time Complexity=O(N) in worst case, space complexity = O(N) in iterative inorder traversal.Solving 2nd case using this solution, would solve 1st case scenario as well unless we are solving 2nd case scenario using other methods like parent pointer etc.
Iterative Solution
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p){
TreeNode* inorder = nullptr;
stack<TreeNode* > s;
TreeNode* curr = root;
Treenode* prev=nullptr;while(curr!=nullptr || !s.empty()){
while(curr!=nullptr){
s.push(curr);
curr = curr->left;
}
TreeNode* temp = s.top();
s.pop();
if(prev == p)
{inorder = temp;break;}
prev = temp;
curr = temp->right;
}
return inorder;
}
Recursive Solution:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode*& prev,TreeNode* p){
if(!root)
return nullptr;
inorderSuccessor(root->left,prev,p);
if(prev == p)
return root;
prev = root;
inorderSuccessor(root->right,prev,p);
}ii) Second way is solving using one of the standard traversals rather than going by use case specific case . Hence above Iterative and Recursive would fall in this case where we are not solving the problem based on the givenNode has right child or not. Time Complexity: O(N) . Both i) and ii) solution is also possible for binary trees as well.
iii) Based on the value of the given Node and applying BST property and converting the question in binary search. Assume the inorder traversal array is given instead of Tree structure, eg: 1,2,3,4,5 where 4 is the root node and 1,2,3 are left child of 4 and 5 is the right child. GivenNode:3 O/P: 4. Hence, root node is given to us which is 4. Root node is equivalent to mid value in binary search.If giveNode<rootNode, we need to find element greater than givenNode, set rootNode as a probable candidate, then search in left subarray which is equivalent to left subtree here and if givenNode>rootNode, we need to search in right subarray.Time complexity : O(logn) since ideally its a binary search where we are discarding half of the array everytime.
void inorderSuccessorUtil(TreeNode* root,TreeNode* &succ, TreeNode* p)
{
TreeNode* curr = root;
while(curr!=nullptr){
if(curr->val> p->val) {
succ=curr;
curr=curr->left;
}
else{
curr=curr->right;
}
}
}Hope this clarifies the above solution. Feel free to share any feedback for the article. Will be sharing posts for other such solutions to develop such thinking approach.
