Sunday, December 13, 2015

Inorder Successor in BST -- Leetcode

Question:
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
Note: If the given node has no in-order successor in the tree, return null.
Answer:
1. Iterative: O(h) + O(1)
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        //case 1 : if p has right subtree
        if(p.right != null){
            return minNode(p.right);
        }
       
        //case 2 : p has no right child, succ is the parent of p
        TreeNode succ = null;
        // Start from root and search for successor down the tree
        while(root != null & root != p){
            if(p.val < root.val){
                succ = root;
                root = root.left;
            }
            else if(p.val > root.val){
                root = root.right;
            }
        }
        return succ;
    }
   
    public TreeNode minNode(TreeNode root){
        if(root==null)return null;
        while(root.left != null){
            root = root.left;
        }
        return root;
    }

2. Recursive: O(h) + O(1)
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        return Util(root, p, null, null);
    }

    public TreeNode Util(TreeNode root, TreeNode p, TreeNode min, TreeNode max){
        if(p.val >= root.val){
            if(root.right != null){
                return Util(root.right, p, root, max);
            }else{
                return max;
            }
        }
        //if p.val < root.val
        else{
            if(root.left != null){
                return Util(root.left, p, min, root);
            }else{
                return root;
            }
        }
    }

No comments:

Post a Comment