Java/Python solution, O(h) time and O(1) space, iterative


  • 183

    The inorder traversal of a BST is the nodes in ascending order. To find a successor, you just need to find the smallest one that is larger than the given value since there are no duplicate values in a BST. It just like the binary search in a sorted list. The time complexity should be O(h) where h is the depth of the result node. succ is a pointer that keeps the possible successor. Whenever you go left the current root is the new possible successor, otherwise the it remains the same.

    Only in a balanced BST O(h) = O(log n). In the worst case h can be as large as n.

    Java

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode succ = null;
        while (root != null) {
            if (p.val < root.val) {
                succ = root;
                root = root.left;
            }
            else
                root = root.right;
        }
        return succ;
    }
    
    // 29 / 29 test cases passed.
    // Status: Accepted
    // Runtime: 5 ms
    

    Python

    def inorderSuccessor(self, root, p):
        succ = None
        while root:
            if p.val < root.val:
                succ = root
                root = root.left
            else:
                root = root.right
        return succ
    
    # 29 / 29 test cases passed.
    # Status: Accepted
    # Runtime: 112 ms

  • 0

    That simple?! Very good understanding of BST.


  • 9
    M

    Simlply elegant!

    I remembered what I've learned in data structure class: to find the successor node in a BST, we need:

    1. first try to find it in p's right subtree;
    2. if p's right subtree is empty, go upwards, go "northwest" till the end, then the first "northeast" node is the successor.

    Based on this thought, I wrote the code as:

    public class Solution {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            if (root==null || p==null) { return null; }
            if (p.right != null) {  // first try to find it in p's right subtree 
                TreeNode q = p.right;
                while (q.left!=null) { q = q.left; }
                return q;
            }  // if not found, next go upwards
            TreeNode succ = dfs(root, p);
            return succ==p ? null : succ;
        }
        
        private TreeNode dfs(TreeNode node, TreeNode p) {
            if (node==null || node==p) { return node; }
            TreeNode left = dfs(node.left, p);
            TreeNode right = dfs(node.right, p);
            if (right == p) { return p; }
            if (left == p) { return node; }
            return left==null? right : left;
        }
    }
    

    After seeing your code, I wonder why my teacher did not teach me this simple way... Then I realize that the teacher's tree node has a field "parent pointer", so we can directly go upwards using it, instead of doing dfs and simulating the "go upwards" process during backtracking.

    I learned a lot from your posts and thank you.


  • 2

    does this code handle the tree with duplicates values and p's value is just one of the duplicate?


  • 0
    B

    This is binary search tree without any duplicate.


  • 2

    Elegant code!

    However I feel it is not optimal when node p is deep in the tree and has right subtree, in which case one only need to search the right subtree to find the successor; but this code need to search all the way down from the root.


  • 2

    @bayesric what if the node has no subtree. In this case, the parent node is the answer and need to be recorded.


  • 0
    T

    @wutong1111 If there's only one node in the tree, then there is no successor


  • 0
    This post is deleted!

  • 0
    K

    Hi @dietpepsi

    Thank you for sharing your idea. I really loved your solution. Could you please share some thought on how would you solve Inorder predecessor with iterative approach?


  • 0
    N

    First judging whether p has right child would be better and decrease running time. For example, adding these lines in the beginning:

    if(p != null && p.right != null){
                root = p.right;
            }
    

  • 0
    R

    Javascript version:

    var inorderSuccessor = function(root, p) {
        var succ = null;
        while(root!=null){
            if(p.val < root.val) {
                succ = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return succ;
    };
    

    C++ version:

    class Solution {
    public:
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            TreeNode* succ = NULL;
            while(root!=NULL){
                if(p->val < root->val) {
                    succ = root;
                    root = root->left;
                } else {
                    root = root->right;
                }
            }
            return succ;
        }
    };
    

  • 0

    said in Java/Python solution, O(h) time and O(1) space, iterative:

    =

    This is the best solution I have ever seen on Leetcode. Thanks @dietpepsi simply genius !!!


  • 1
    R

    @dietpepsi Amazing solution !! Kudos to you for coming up with this solution :)


  • 0
    R

    @dietpepsi Similar logic could be applied to find the Predecessor as well. Awesome :)


  • 0
    B

    similar idea, maybe look more like doing binary search.

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
             TreeNode cur = root;
             TreeNode lo = null;
             TreeNode hi = null;
             while (cur != null) {
                   if (cur.val <= p.val) {
                       lo = cur;
                       cur = cur.right;
                   } else {
                       hi = cur;
                       cur = cur.left;
                   }    
             }
             return hi;
         }

  • 0
    Q

    Impressive and concise code! Find the Predecessor in BST can be deal with the same trick, following is the code

        public  TreeNode inorderPerdecessor(TreeNode root, TreeNode p) {
            TreeNode predecessor = null;
            while (root != null) {
                if (root.val < p.val) {
                    predecessor = root;
                    root = root.right;
                } else {
                    root = root.left;
                }
            }
            return predecessor;
        }
    

  • 0
    R

    why has no one checked if the root of which we have to find in order successor has a right child or not, because if it has a right child we dont need to traverse the whole height of the tree, we can simple find lowest value node in its right subtree.


  • 0
    M

    @rishp The algorithm does exactly the same thing what you mentioned.


  • 1
    M

    What an amazing solution !! Below is version of predecessor inspired by this. Took me a bit to understand the logic behind how successor and predecessor works with this logic. For people like me :) , below is a little explanation that might help understand.

    Inorder Successor:
    First of all, what is inorder successor ?

    • It is the immediately bigger node than current node. If a node has right subtree, it is the smallest node found in the right subtree.
    • If the right subtree is null, it is the last node whose left subtree you are under.

    How the algorithm finds it ?
    On equality of the value whose inorder successor we are after, it makes it go to the right subtree. As all elements in the right subtree are larger than the current node, from that point onward the algorithm will be drawn towards finding the smallest value in right subtree. As we keep traversing down smaller nodes, we modify value of successor.

    Inorder Predecessor
    It is pretty much the same concept as successor.

    • If the left subtree exist, predecessor is the largest node found in left subtree.
    • If the left subtree does not exist, it is the last node whose right subtree the node is under.

    How the algorithm finds it ?
    On equality of the value whose inorder predecessor we are after, it makes traversal go to the left subtree. As all elements in leftsubtree are smaller than the node's value, algorithm will be drawn towards the largest value in that subtree. As we keep going right, we update the predecessor.

    public  TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
        	if(root == null || p == null){return null;}
        	
        	TreeNode predecessor = null;
        	while(root != null){
        		if(p.val <= root.val){
        			root = root.left;
        		}else{
        			predecessor = root;
        			root = root.right;
        		}
        	}
        	return predecessor;
        }
    

Log in to reply
 

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