Inorder Successor in BST

https://leetcode.com/problems/inorder-successor-in-bst

# Definition for a Binary Tree Node

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# Solution

Let hh be the height of tree.

Complexity:

  • time: O(h)O(h)
  • space: O(h)O(h)

# Iteration I

def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
    if not root:
        return None
    lowest_right_father = None
    # find lowest right father, if any
    while root!=p:
        if root.val < p.val:
            root = root.right
        else:
            lowest_right_father = root
            root = root.left
    # find leftmost node of right subtree, if any
    son = p.right
    res = son
    while son:
        res = son
        son = son.left
    if not res:
        return lowest_right_father
    return res

# Iteration II

def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
    if not root:
        return None
    res = None
    while root:
        if root.val <= p.val:
            root = root.right
        else:
            if res is None or res.val > root.val:
                res = root
            root = root.left
    return res
Last Updated: 7/19/2020, 3:45:14 PM