# 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) { 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; } }; 
  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; } }