How hard is LeetCode 510. Inorder Successor in BST II?

LeetCode 510. Inorder Successor in BST II is rated Medium on LeetCode.

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

The Python solution on this page runs in O(h), where h is the height of the binary tree.

What is the space complexity of LeetCode 510. Inorder Successor in BST II?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 510. Inorder Successor in BST II cover?

LeetCode 510. Inorder Successor in BST II is tagged Tree, Binary Search Tree and Binary Tree on LeetCode.

Is LeetCode 510. Inorder Successor in BST II a premium problem?

Yes. LeetCode 510. Inorder Successor in BST II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Inorder Successor in BST II — LeetCode 510 Python Solution

MediumLeetCode PremiumTreeBinary Search TreeBinary Tree

Problem: #510
Pattern: Tree Traversal
Reading time: 4 min
Source: leetcode.com

The problem

Given a node in a binary search tree, return the in-order successor of that node in the BST. If that node has no in-order successor, return null.

Example

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

Python solution

Python

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':
        if node.right:
            node = node.right
            while node.left:
                node = node.left
            return node
        while node.parent and node.parent.right is node:
            node = node.parent
        return node.parent

Complexity

Measure	Complexity
Time	O(h), where h is the height of the binary tree
Space	O(1) auxiliary

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 510. Inorder Successor in BST II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Tree, Binary Tree and Binary Search Tree.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 510. Inorder Successor in BST II?: LeetCode 510. Inorder Successor in BST II is rated Medium on LeetCode.
What is the time complexity of LeetCode 510. Inorder Successor in BST II?: The Python solution on this page runs in O(h), where h is the height of the binary tree.
What is the space complexity of LeetCode 510. Inorder Successor in BST II?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 510. Inorder Successor in BST II cover?: LeetCode 510. Inorder Successor in BST II is tagged Tree, Binary Search Tree and Binary Tree on LeetCode.
Is LeetCode 510. Inorder Successor in BST II a premium problem?: Yes. LeetCode 510. Inorder Successor in BST II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.