Inorder Predecessor in BST

https://www.lintcode.com/problem/inorder-predecessor-in-bst

# Definition for a Binary Tree Node

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

# Solution

Let hh be the height of tree.

Complexity:

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

# Iteration I

def inorderPredecessor(self, root, p):
    if not root:
        return None
    lowest_left_father = None
    # find lowest left father, if any
    while root!=p:
        if root.val < p.val:
            lowest_left_father = root
            root = root.right
        else:
            root = root.left
    # find rightmost node of left subtree, if any
    son = p.left
    res = son
    while son:
        res = son
        son = son.right
    if not res:
        return lowest_left_father
    return res

# Iteration II

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