in-order successor of node in binary search tree

//example
   4
 2       6
1 3   5    7
     5 6

// cases:
next(3) = 4

// corner cases:
next(7) = null
next(null) = 1

With parent node pointer.

node:
    left, right
    parent
// parent node pointer. O(logn).
(n, root):
    next == null
    if n == null:
        // return leftmost of root
        if root == null:
            throw
        next = root
        while next.left != null:
            next = next.left
    else if n.right != null:
        // return leftmost of right child
        next = n.right
        while next.left != null:
            next = next.left
    else:
        // go up till next is parent's right child, return its parent
        next = n
        while next.parent != null && next.parent.right == next:
            next = next.parent
        next = next.parent        
    return next

[Hat tip to ctci]

Without parent node pointer. prev is wrapped as its value needs to be retained through calls as for next(3) = 4.

// no parent node pointer. O(n).
(x, root):
    if root == null: // x = null is ok
        throw
    return (root, x, prev = { value: null })

(n, x, prev):
    if n == null:
        return null
    next = (n.left, x, prev)
    if next != null:
        return next
    if prev.value == x:
        return n
    prev.value = n
    next = (n.right, x, prev)
    if next != null:
        return next
    return null

For in-order predecessor, just a small change.

    if n == x:
        return prev.value