Ziyuan Qin's blog

Inorder Successor in BST

TreeMorris
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
1
2
3
4
5

# Solution

Let hh be the height of tree.

Complexity

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

# Vanilla Iteration

Return the leftmost node of right subtree, if any; otherwise, return the lowest right father instead.

def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
    if not root:
        return None
    lowest_right_father = None
    # find lowest right father
    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
    son = p.right
    res = son
    while son:
        res = son
        son = son.left
    if not res:
        return lowest_right_father
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# DFS

# Iteration

Algorithm:

  • if current node's value is less than or equal to p's value, we know our answer must be in the right subtree
  • if current node's value is greater than p's value, current node is a candidate. Go to its left subtree to see if we can find a smaller one
  • if we reach null, our search is over, just return the candidate
def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
    res = None
    node = root
    while node:
        if node.val <= p.val:
            node = node.right
        else:
            res = node
            node = node.left
    return res
1
2
3
4
5
6
7
8
9
10

# Recursion

def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
    res = None
    def dfs(root, p):
        nonlocal res
        if not root:
            return
        if root.val <= p.val:
            dfs(root.right, p)
        else:
            res = root
            dfs(root.left, p)

    dfs(root, p)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Integer to Roman