Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

510. Inorder Successor in BST II

Time: $O(h)$

Space: $O(1)$

			


class Solution {
 public:
  Node* inorderSuccessor(Node* node) {
    // The successor is somewhere lower in the right subtree
    if (node->right) {
      node = node->right;
      while (node->left)
        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;
  }
};




			


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;
  }
}