Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.


Binary Search

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null || p == null) return null;
        else if(p.right != null){
            // find successor directly
            p = p.right;
            while(p.left != null)
                p = p.left;
            return p;
        }else{

            //binary search to find p and prev node
            TreeNode curr = root, prev = null;

            while(curr != p){
                if(curr.val > p.val){
                    prev = curr;
                    curr = curr.left;
                }else{
                    curr = curr.right;
                }

            }
            return prev;
        }
    }

O(n), flat BST to list.

private List<TreeNode> flatList = new ArrayList<>();

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null || p == null)
            return null;
        inorderTraversal(root);
        for(int i = 0; i < flatList.size(); i++){
            if(flatList.get(i) == p && i + 1 < flatList.size())
                return flatList.get(i + 1);
        }
        return null;
    }

    private void inorderTraversal(TreeNode root){
        if(root == null)
            return;
        inorderTraversal(root.left);
        flatList.add(root);
        inorderTraversal(root.right);
    }

results matching ""

    No results matching ""