1. Binary tree:
The successor of a node p is the node with the smallest key greater than p.val.
So there can be three cases to find the successor of a node:
- If the node has the right child, the successor must reside in its right subtree. If not, go to case 2. Note that, I didn’t mention the right “child”, I mentioned “subtree”. Because the node’s right child may not have the smallest value greater than p.value. In that case, the smallest value would be the leftmost child of the right child.
- If the node has no right child, then in the inorder traversal process, the successor node to be traversed would be this(node p’s) subtree’s parent node, which is the immediate node in the stack. If the stack is empty already, then go to case 3.
- If case 1 and 2 fails, that means node p has no successor.
We can use this process to find the inorder successor of a BST(Binary Search Tree) too. But in that case, we are not using the properties of BST, so that won’t be optimized. That is, this code’s time and space complexity is O(N), N being the number of nodes. In the case of BST, if we use the BST properties, then this problem can be solved in O(N) time and O(1) space.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
stack<TreeNode*> st;
TreeNode *node=root;
bool c=0;
while(!st.empty() || node)
{
while(node)
{
st.push(node);
node=node->left;
}
node=st.top();
st.pop();
if(c==1) return node;
if(node==p)
{
c=1;
if(!node->right)
{
if(!st.empty()) return st.top();
else return NULL;
}
}
node=node->right;
}
return NULL;
}
};
2. Binary Search Tree:
Here using the BST properties, each time, we will discard half of the tree. Thus our usual time complexity for a balanced binary tree would be logarithmic instead of linear i.e. O(log(N)), and our space complexity would be constant i.e O(1) as we are not using any extra data structure to store the tree. Though in case the BST is not balanced, so we will get a skewed tree, in that worst-case scenario, the time complexity would be O(N).
Here, all the above 3 cases are taken care of at once.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
TreeNode *node=root;
TreeNode *successor=NULL;
while(node)
{
if(node->val > p->val)
{
successor=node;
node=node->left;
}
else if(node->val <= p->val)
{
node=node->right;
}
}
return successor;
}
};
Fall out, Codes! 