How hard is LeetCode 285. Inorder Successor in BST?

LeetCode 285. Inorder Successor in BST is rated Medium on LeetCode.

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

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

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

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

What topics does LeetCode 285. Inorder Successor in BST cover?

LeetCode 285. Inorder Successor in BST is tagged Tree, Depth-First Search, Binary Search Tree and Binary Tree on LeetCode.

Is LeetCode 285. Inorder Successor in BST a premium problem?

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

Inorder Successor in BST — LeetCode 285 Python Solution

MediumLeetCode PremiumTreeDepth-First SearchBinary Search TreeBinary Tree

Problem: #285
Pattern: Tree Traversal
Reading time: 3 min
Source: leetcode.com

The problem

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

Example

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

Python solution

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
        ans = None
        while root:
            if root.val > p.val:
                ans = root
                root = root.left
            else:
                root = root.right
        return ans

Complexity

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

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 285. Inorder Successor in BST is filed here because LeetCode tags it Tree, Binary Tree and Binary Search Tree, which is the vocabulary this hub collects.

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 285. Inorder Successor in BST?: LeetCode 285. Inorder Successor in BST is rated Medium on LeetCode.
What is the time complexity of LeetCode 285. Inorder Successor in BST?: The Python solution on this page runs in O(h), where h is the height of the binary search tree.
What is the space complexity of LeetCode 285. Inorder Successor in BST?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 285. Inorder Successor in BST cover?: LeetCode 285. Inorder Successor in BST is tagged Tree, Depth-First Search, Binary Search Tree and Binary Tree on LeetCode.
Is LeetCode 285. Inorder Successor in BST a premium problem?: Yes. LeetCode 285. Inorder Successor in BST is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.