I recently encountered with a question in an interview at e-commerce company. The interviewer asked the following question:
There is BST given with root node with key part as integer only. The structure of each node is as follows:
[pastacode lang=”c” manual=”struct%20Node%0A%7B%0A%20%20%20%20int%20key%3B%0A%20%20%20%20struct%20Node%20*left%2C%20*right%20%3B%0A%7D%3B” message=”” highlight=”” provider=”manual”/]You need to find the inorder successor and predecessor of a given key. In case the given key is not found in BST, then return the two values within which this key will lie.
[ad type=”banner”]Following is the algorithm to reach the desired result. Its a recursive method:
Input: root node, key
output: predecessor node, successor node
1. If root is NULL
then return
2. if key is found then
a. If its left subtree is not null
Then predecessor will be the right most
child of left subtree or left child itself.
b. If its right subtree is not null
The successor will be the left most child
of right subtree or right child itself.
return
3. If key is smaller then root node
set the successor as root
search recursively into left subtree
else
set the predecessor as root
search recursively into right subtree
[ad type=”banner”]
Following is C++ implementation of the above algorithm:
[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20find%20predecessor%20and%20successor%20in%20a%20BST%0A%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20BST%20Node%0Astruct%20Node%0A%7B%0A%20%20%20%20int%20key%3B%0A%20%20%20%20struct%20Node%20*left%2C%20*right%3B%0A%7D%3B%0A%20%0A%2F%2F%20This%20function%20finds%20predecessor%20and%20successor%20of%20key%20in%20BST.%0A%2F%2F%20It%20sets%20pre%20and%20suc%20as%20predecessor%20and%20successor%20respectively%0Avoid%20findPreSuc(Node*%20root%2C%20Node*%26%20pre%2C%20Node*%26%20suc%2C%20int%20key)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20case%0A%20%20%20%20if%20(root%20%3D%3D%20NULL)%20%20return%20%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20key%20is%20present%20at%20root%0A%20%20%20%20if%20(root-%3Ekey%20%3D%3D%20key)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20the%20maximum%20value%20in%20left%20subtree%20is%20predecessor%0A%20%20%20%20%20%20%20%20if%20(root-%3Eleft%20!%3D%20NULL)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20Node*%20tmp%20%3D%20root-%3Eleft%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(tmp-%3Eright)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tmp%20%3D%20tmp-%3Eright%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20pre%20%3D%20tmp%20%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20the%20minimum%20value%20in%20right%20subtree%20is%20successor%0A%20%20%20%20%20%20%20%20if%20(root-%3Eright%20!%3D%20NULL)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20Node*%20tmp%20%3D%20root-%3Eright%20%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(tmp-%3Eleft)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tmp%20%3D%20tmp-%3Eleft%20%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20suc%20%3D%20tmp%20%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20key%20is%20smaller%20than%20root’s%20key%2C%20go%20to%20left%20subtree%0A%20%20%20%20if%20(root-%3Ekey%20%3E%20key)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20suc%20%3D%20root%20%3B%0A%20%20%20%20%20%20%20%20findPreSuc(root-%3Eleft%2C%20pre%2C%20suc%2C%20key)%20%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%20%2F%2F%20go%20to%20right%20subtree%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20pre%20%3D%20root%20%3B%0A%20%20%20%20%20%20%20%20findPreSuc(root-%3Eright%2C%20pre%2C%20suc%2C%20key)%20%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20new%20BST%20node%0ANode%20*newNode(int%20item)%0A%7B%0A%20%20%20%20Node%20*temp%20%3D%20%20new%20Node%3B%0A%20%20%20%20temp-%3Ekey%20%3D%20item%3B%0A%20%20%20%20temp-%3Eleft%20%3D%20temp-%3Eright%20%3D%20NULL%3B%0A%20%20%20%20return%20temp%3B%0A%7D%0A%20%0A%2F*%20A%20utility%20function%20to%20insert%20a%20new%20node%20with%20given%20key%20in%20BST%20*%2F%0ANode*%20insert(Node*%20node%2C%20int%20key)%0A%7B%0A%20%20%20%20if%20(node%20%3D%3D%20NULL)%20return%20newNode(key)%3B%0A%20%20%20%20if%20(key%20%3C%20node-%3Ekey)%0A%20%20%20%20%20%20%20%20node-%3Eleft%20%20%3D%20insert(node-%3Eleft%2C%20key)%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20node-%3Eright%20%3D%20insert(node-%3Eright%2C%20key)%3B%0A%20%20%20%20return%20node%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20key%20%3D%2065%3B%20%20%20%20%2F%2FKey%20to%20be%20searched%20in%20BST%0A%20%0A%20%20%20%2F*%20Let%20us%20create%20following%20BST%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%2050%0A%20%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%20%20%5C%0A%20%20%20%20%20%20%20%20%20%2030%20%20%20%20%20%2070%0A%20%20%20%20%20%20%20%20%20%2F%20%20%5C%20%20%20%20%2F%20%20%5C%0A%20%20%20%20%20%20%2020%20%20%2040%20%2060%20%20%2080%20*%2F%0A%20%20%20%20Node%20*root%20%3D%20NULL%3B%0A%20%20%20%20root%20%3D%20insert(root%2C%2050)%3B%0A%20%20%20%20insert(root%2C%2030)%3B%0A%20%20%20%20insert(root%2C%2020)%3B%0A%20%20%20%20insert(root%2C%2040)%3B%0A%20%20%20%20insert(root%2C%2070)%3B%0A%20%20%20%20insert(root%2C%2060)%3B%0A%20%20%20%20insert(root%2C%2080)%3B%0A%20%0A%20%0A%20%20%20%20Node*%20pre%20%3D%20NULL%2C%20*suc%20%3D%20NULL%3B%0A%20%0A%20%20%20%20findPreSuc(root%2C%20pre%2C%20suc%2C%20key)%3B%0A%20%20%20%20if%20(pre%20!%3D%20NULL)%0A%20%20%20%20%20%20cout%20%3C%3C%20%22Predecessor%20is%20%22%20%3C%3C%20pre-%3Ekey%20%3C%3C%20endl%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20cout%20%3C%3C%20%22No%20Predecessor%22%3B%0A%20%0A%20%20%20%20if%20(suc%20!%3D%20NULL)%0A%20%20%20%20%20%20cout%20%3C%3C%20%22Successor%20is%20%22%20%3C%3C%20suc-%3Ekey%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20cout%20%3C%3C%20%22No%20Successor%22%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C++ Programming” highlight=”” provider=”manual”/]Output:
Predecessor is 60 Successor is 70