LeetCode 510: Inorder Successor in BST II Solution

Master LeetCode problem 510 (Inorder Successor in BST II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

510. Inorder Successor in BST II

Medium

Tree Binary Search Tree Binary Tree

Problem Explanation

Explanation

In this problem, we are given a node in a binary search tree (BST) and we need to find the inorder successor of that node. The inorder successor of a node is the node with the smallest key greater than the node's key.

To solve this problem, we can follow these steps:

If the given node has a right child, then the inorder successor is the leftmost node in the right subtree.
If the given node does not have a right child, then we need to traverse up the tree until we find a node that is the left child of its parent. The parent node of such a node will be the inorder successor.

By following these steps, we can find the inorder successor for the given node efficiently.

Time complexity: O(h), where h is the height of the tree. Space complexity: O(1).

Solution Code

public Node inorderSuccessor(Node node) {
    if (node.right != null) {
        Node curr = node.right;
        while (curr.left != null) {
            curr = curr.left;
        }
        return curr;
    } else {
        Node parent = node.parent;
        while (parent != null && node == parent.right) {
            node = parent;
            parent = parent.parent;
        }
        return parent;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 510 (Inorder Successor in BST II)?

This page provides optimized solutions for LeetCode problem 510 (Inorder Successor in BST II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 510 (Inorder Successor in BST II)?

The time complexity for LeetCode 510 (Inorder Successor in BST II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 510 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 510 in Java, C++, or Python.

Back to LeetCode Solutions