Skip to content

510. Inorder Successor in BST II 👍

  • Time: $O(h)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  Node* inorderSuccessor(Node* node) {
    // The successor is somewhere lower in the right subtree.
    if (node->right != nullptr) {
      node = node->right;
      while (node->left != nullptr)
        node = node->left;
      return node;
    }

    // The successor is somewhere upper in the tree.
    while (node->parent && node->parent->left != node)
      node = node->parent;
    return node->parent;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public Node inorderSuccessor(Node node) {
    // The successor is somewhere upper in the tree.
    if (node.right == null) {
      while (node.parent != null && node.parent.left != node)
        node = node.parent;
      return node.parent;
    }

    // The successor is somewhere lower in the right subtree.
    node = node.right;
    while (node.left != null)
      node = node.left;
    return node;
  }
}