[285. Inorder Successor in BST] #leetcode

285_0903.java

// O(n) O(1) 
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) return null;
        
        TreeNode succ = null;
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.right;
            } else {
                TreeNode node = stack.pop();
                if (node == p) return succ;
                succ = node;
                root = node.left;
            }
             
        }
        return succ;
    }
}

// O(log(n))
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;
    }
}