Inorder Successor in BST


  • 0
    H

    Here is a link to this problem: https://leetcode.com/problems/inorder-successor-in-bst/description/

    This is a very simple problem. We can use a simple binary search combined with dfs to tackle this. First, we look for node 'P' in the tree. If we don't find it, then there is not successor. As we look for this node 'P' using standard binary search approach (if smaller then move to left, otherwise move to right), we put the nodes we encounters in a stack. Thus when we find 'P', we also have a stack with nodes in path from 'root' to 'P'.

    If 'P' has a right child, then look for the smallest element in the right child. This can be easily achieved with following piece of code

    if (p->right) {p=p->right; while(p->left) p=p->left; return p;}
    

    Otherwise, pop nodes from parents stack until you find one with value higher than that of 'P'. This is achieved with following code:

    while(parent.top() && parent.top()->val < p->val)
                parent.pop();
    
    return parent.top();
    
    

    class Solution {
    public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {

        stack<TreeNode*> parent; parent.push(nullptr);
        
        while(root && root!=p)
        {
            parent.push(root);
            if (p->val < root->val) root=root->left;
            else if (p->val > root->val) root=root->right;            
        }
        
        if (!root) return nullptr;      
        
        if (p->right)
        {
            p=p->right; while(p->left) p=p->left; return p;
        }
        
        while(parent.top() && parent.top()->val < p->val)
            parent.pop();
        
        return parent.top();
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.