Share my Java recursive solution


  • 238

    Just want to share my recursive solution for both getting the successor and predecessor for a given node in BST.

    Successor

    public TreeNode successor(TreeNode root, TreeNode p) {
      if (root == null)
        return null;
    
      if (root.val <= p.val) {
        return successor(root.right, p);
      } else {
        TreeNode left = successor(root.left, p);
        return (left != null) ? left : root;
      }
    }
    

    Predecessor

    public TreeNode predecessor(TreeNode root, TreeNode p) {
      if (root == null)
        return null;
    
      if (root.val >= p.val) {
        return predecessor(root.left, p);
      } else {
        TreeNode right = predecessor(root.right, p);
        return (right != null) ? right : root;
      }
    }

  • 41

    Very nice! I wish I had thought of that.

    Here's just a small variation, mainly using a loop instead of the recursion-to-right:

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        while (root != null && root.val <= p.val)
            root = root.right;
        if (root == null)
            return null;
        TreeNode left = inorderSuccessor(root.left, p);
        return (left != null && left.val > p.val) ? left : root;
    }
    

    And another:

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        while (root != null && root.val <= p.val)
            root = root.right;
        TreeNode left = root == null ? null : inorderSuccessor(root.left, p);
        return (left != null && left.val > p.val) ? left : root;
    }
    

  • 3

    Thanks Stefan, actually I learn a lot from your solutions!


  • 0
    C

    return (left != null && left.val > p.val) ? left : root
    could be simplified to
    return (left != null) ? left : root


  • 0
    H
    This post is deleted!

  • 0
    S

    yes, just find out the left-most node, because this is BST


  • 0

    Thank you guys!


  • 2
    J

    left.val > p.val this can be ignored.


  • 0

    @Jinx_boom Thanks, you're right.

    Judging by a Ruby solution I wrote based on this (posted now), I apparently noticed it but then forgot about it... strange.


  • 0
    F

    Can anyone help to explain when the predecessor() can return a not null value?


  • 5

    The solution is clear, but it seems it cannot detect whether p is inside of tree or not. And this seems cannot deal with tree with duplicate value and p's value is one of the duplicate.


  • 0

    This solution is nice, but I still cannot understand return (left != null) ? left : root; Can anyone explain it? Thank you!


  • 34

    Hi @xietao0221, let's take the successor for example, basically we always want to find p's closest node (in inorder traversal) and the node's value is larger than p's value, right? That node can either be p's parent or the smallest node in p' right branch.

    When the code runs into the else block, that means the current root is either p's parent or a node in p's right branch.

    If it's p's parent node, there are two scenarios: 1. p doesn't have right child, in this case, the recursion will eventually return null, so p's parent is the successor; 2. p has right child, then the recursion will return the smallest node in the right sub tree, and that will be the answer.

    If it's p's right child, there are two scenarios: 1. the right child has left sub tree, eventually the smallest node from the left sub tree will be the answer; 2. the right child has no left sub tree, the recursion will return null, then the right child (root) is our answer.

    I guess it's hard to understand unless you draw different scenarios out. :)


  • 0

    Thank you for your reply, your explanation is perfect, finally I know these four scenarios. Thank you so much!!!
    BTW, you'd better add this part of words on your solution.


  • 0
    S

    @xietao0221 yes, I agree with you. If p is not in the BST, but the BST has nodes whose values are larger than p's, this solution still has a not-null return.


  • 0
    L

    do you consider the cases where there are duplicates (let's say every node has the same value, but p points to the left most one. your program will keeps going to the right and return null.) in the case below, a root has a left and right child, p points to the left child, we should return root, yet your program will return null, right?
    -------------2 <-root
    p------>2-----2
    and the other case is there is no node p in the tree (you algorithm will return some node, but if p is not in the tree, I think we should return null, right?)
    Thanks


  • 0
    R

    Hi @jeantimex :

    I feel that there is a small bug in your code:

    If the BST has duplicate nodes and the given node is P which is to the left of the current root (in a recursive call) but root.val == p.val, then in this case your code, will incorrectly return successor(root.right, p).

    Correct me if I'm wrong?


  • 1
    S

    Awesome algorithm! For me took a while to grasp the idea. Here is my less sexy but probably with a little but less magic version derived from your code...

    TreeNode lastLeftParent;
    
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        lastLeftParent = null;
        successor(root, p);
        return lastLeftParent;
    }
    
    public void successor(TreeNode root, TreeNode p) {
        if (root != null) {
            if (p.val >= root.val) successor(root.right, p);
            else {
                lastLeftParent = root;
                successor(root.left, p);
            }
        }
    }

  • 0
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            if(root == null) return null;
            
            if(root.val <= p.val){
                return inorderSuccessor(root.right, p);
            } else {
                // if (left == null) means on the left nodes of this root, no any node has value between this root and the target P.
                // so return this root, otherwise recusively go to root.left.
                TreeNode left = inorderSuccessor(root.left, p);
                return left == null ? root: left;
            }
        }

  • 0
    M
    This post is deleted!

Log in to reply
 

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