Binary Search Tree

Overview

A binary search tree (BST) is a binary tree satisfying the binary-search-tree property:

Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$, then $y.key\le x.key$. If $y$ is a node in the right subtree of $x$, then $y.key\ge x.key$.

Traversals

Consider an arbitrary node $x$ of some BST. Then:

• An inorder traversal visits $x$‘s left child, then $x$, then $x$‘s right child.
• A preorder traversal visits $x$, then $x$‘s left child, then $x$‘s right child.
• A postorder traversal visits $x$‘s left child, then $x$‘s right child, then $x$.

Successors

The successor of a node in a binary search tree is the node whose value would appear immediately after in an in-order traversal.

Predecessors

The predecessor of a node in a binary search tree is the node whose value would appear immediately before in an in-order traversal.

Deletions

Consider deleting node $z$ from a BST. There are three conceptual cases to consider corresponding to the number of children $z$ has:

• If $z$ has no children we can just replace $z$ with NIL.
• If $z$ has one child, we can replace $z$ with its child.
• If $z$ has two children, we swap $z$ with either its predecessor or successor, updating pointers as necessary to maintain the binary-search-tree property.

Bibliography

• Donald Ervin Knuth, Art of Computer Programming, 3: Sorting and Searching, 2. ed., 34. (Reading, Mass: Addison-Wesley, 1995).
• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).