510. Inorder Successor in BST II

 一刷 07/2022

Version #1 Intuitive Solution

Algorithm

If the node has a right child, and hence its successor is somewhere lower in the tree. Go to the right once and then as many times to the left as you could. Return the node you end up with.

Node has no right child, and hence its successor is somewhere upper in the tree. Go up till the node that is left child of its parent. The answer is the parent.

Runtime: 34 ms, faster than 84.80% of Java online submissions for Inorder Successor in BST II.

Memory Usage: 43.5 MB, less than 97.28% of Java online submissions for Inorder Successor in BST II.

/*

// Definition for a Node.

class Node {

    public int val;

    public Node left;

    public Node right;

    public Node parent;

};

*/

class Solution {

    public Node inorderSuccessor(Node node) {

        // 1. on the right subtree of node

        if (node == null) {

            return null;

        }

        if (node.right != null) {

            return findSmallest(node.right);

        }

        // 2. node is the child of the parent tree

        //      parent

        //       / \

        //         node 

        Node child = node;

        while (child.parent != null) {

            if (child.parent.left == child) {

                return child.parent;

            }

            child = child.parent;

        }

        return null;

    }

    

    // Returns the smallest node

    private Node findSmallest(Node root) {

        Node node = root;

        while (node != null && node.left != null) {

            node = node.left;

        }

        return node;

    }

}