Inorder Successor in BST

Problem Id: 285 Difficulty: Medium Tag: Tree


Intuition

The successor of a node is the next visited node in inorder traversal. So it's either its parent or the left most leaf of its right subtree. So we could get the result by the following algorithm.

First, do a binary search and get the node p. While we do this binary search, we should always save the parent node of current node.

Once we get the node p, we could get the successor of the node by following way. If its right node is None, the successor if its parent. If its right node is not None, it's successor is the left most leaf of its right sub-tree.

Solution


# 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') -> 'TreeNode':
        parent = None
        node = root
        while node and node != p:
            if node.val < p.val:
                node = node.right
            else:
                parent = node
                node = node.left

        if node is None:
            return None
        if node.right is None:
            return parent
        else:
            successor = node.right
            while successor.left:
                successor = successor.left
            return successor