## Binary Search Tree: In-Order Predecessor And Successor

### February 12, 2013

We begin with some necessary infrastructure for handing binary search trees; our trees have only keys, not values, but you can add those yourself:

`(define (tree key lkid rkid) (vector key lkid rkid))`

```(define (key tree) (vector-ref tree 0)) (define (lkid tree) (vector-ref tree 1)) (define (rkid tree) (vector-ref tree 2))```

```(define nil (vector 'nil 'nil 'nil)) (vector-set! nil 1 nil) (vector-set! nil 2 nil) (define (nil? tree) (eqv? tree nil))```

```(define (insert lt? t k)   (cond ((nil? t) (tree k nil nil))         ((lt? k (key t)) (tree (key t) (insert lt? (lkid t) k) (rkid t)))         ((lt? (key t) k) (tree (key t) (lkid t) (insert lt? (rkid t) k)))   (else t)))```

Next we write two functions that are subroutines to the `predecessor` and `successor` functions as well as being useful in their own right. The `minimum` function finds the smallest key in the tree by chasing left sub-trees; the `maximum` function finds the largest key in the tree by chasing right sub-trees:

```(define (minimum t)   (cond ((nil? t) #f)         ((nil? (lkid t)) (key t))         (else (minimum (lkid t)))))```

```(define (maximum t)   (cond ((nil? t) #f)         ((nil? (rkid t)) (key t))         (else (maximum (rkid t)))))```

Now we are ready for the `predecessor` and `successor` functions. There are three returns and two recursive calls in each function. The first and fourth `cond` clauses return the saved tree when the recursion reaches a null node because the target key does not exist. The fifth clause returns the minimum/maximum when the search key is found. The other two clauses recur. Note that one of the clauses resets the saved tree as it recurs; the saved tree is the parent of the leftmost/rightmost non-matching node, and is the return value if the search key is found at a leaf of the tree:

```(define (pred lt? t k)   (define (return t) (if (nil? t) #f (key t)))   (let loop ((t t) (prev nil))     (cond ((nil? t) (return prev))           ((lt? (key t) k) (loop (rkid t) t))           ((lt? k (key t)) (loop (lkid t) prev))           ((nil? (lkid t)) (return prev))           (else (maximum (lkid t))))))```

```(define (succ lt? t k)   (define (return t) (if (nil? t) #f (key t)))   (let loop ((t t) (next nil))     (cond ((nil? t) (return next))           ((lt? k (key t)) (loop (lkid t) t))           ((lt? (key t) k) (loop (rkid t) next))           ((nil? (rkid t)) (return next))           (else (minimum (rkid t))))))```

You can see the complete code, along with a small set of examples, at http://programmingpraxis.codepad.org/PkWVHKLi.

Pages: 1 2

### 3 Responses to “Binary Search Tree: In-Order Predecessor And Successor”

1. jpverkamp said

Here’s a version in Racket: Predecessor and successor in a binary search tree

I went a slightly different direction than the solution here with a shared function to return the node containing the value we were searching for and the last left and right branch all at once (the ability to return multiple `value`s is always nice). That made the actual `predecessor` and `successor` functions somewhat simpler:

```; get the predecessor to a value
(define (predecessor tr < val)
(define-values (l v r) (find-nodes tr < val))
(cond
[(tree-left? v)
(maximum (tree-left v))]
[(and (not (void? r)) (not (empty? r)))
(tree-value r)]))
```

I also included code for using this to implement a sorting algorithm. Dump everything into a tree, find the `minimum`, then repeatedly call `successor` until you run out of elements. Am I incorrect in thinking that this is actually still `O(n log n)`, albeit with a higher constant than most? It sorts a million element list only about 3x slower than a naive implementation of `quicksort` did, but insertion sort (known `O(n^2)`) didn’t even finish before I got bored.

2. I finally got around to this challenge. Here’s the code for successor in python.

```class Node:
def __init__(self, val=None, l=None, r=None):
self.l = l
self.r = r
self.val = val

def insert(node, val):
if node == None:
return
elif node.val == val:
return
elif node.val > val:
if node.l is None:
node.l = Node(val)
else:
insert(node.l, val)
else:
if node.r is None:
node.r = Node(val)
else:
insert(node.r, val)

def suc(node, val, ancestor=Node(None)):
'''
>>> mynode = Node(5)
>>> for v in "6 12 8 3 2 5 3 4 11 7 1".split():
...     insert(mynode,int(v))
>>> suc(mynode,5)
6
>>> suc(mynode,8)
11
>>> suc(mynode,11)
12
>>> suc(mynode,12)

>>> suc(mynode,2)
3
>>> suc(mynode,9)
11
>>> suc(mynode,15)

'''
if node is None:
return ancestor.val
if node.val == val:
if node.r is None:
return ancestor.val
else:  # Find leftmost of right node
node = node.r
while node.l is not None:
node = node.l
return node.val
elif node.val > val:
return suc(node.l, val, node)
else:
return suc(node.r, val, ancestor)

```