Binary Search Trees

Left child smaller, right child bigger.

You should start by reading about binary search before reading this page. It assumes you understand that page.

Briefly, we applied binary search by recursively partitioning a sorted array into two pieces, doing one comparison, and then eliminating one (or both, if we found what we were looking for) partition.

Now lets consider a slightly different way of drawing the sorted array:

• This is actually much more than just redrawing the sorted array in a different way.
• You'll notice that as you work your way from left to right, the elements in the lower figure are still in sorted order.
• The bottom part of the figure represents a binary search tree.
• A binary search tree must adhere to the following rules:
  • There is one element at the top, called the root
  • Each element can have at most two elements directly below it, called children
  • The left child must be less than its parent
  • The right child must be greater than its parent¹
• Performing a binary search on a binary search tree is a simple matter of recursively working our way down the tree.
  • If the element we are looking for is less than the current element, we go to the left child
  • If the element we are looking for is greater than the current element, we go to the right child
  • Otherwise, we have found our element and we are ready to stop
• If we make it to the bottom of the tree without encountering the value we are looking for, we can be certain that it is not present in our data structure.

Tree Terminology

• A tree is said to be a binary tree if each element can have zero, one, or two children.
• Each element in the tree is called a node.
• The top-most node is called the root.
• The root and all of the nodes connected to it are called a tree.
• Any node and all of the nodes connected below it are called a subtree.
• A node directly above another node is called its parent.
• A node directly below and to the left of another node is called its left child.
• A node directly below and to the right of another node is called its right child.
• A tree is said to be a binary search tree if every left child is smaller than its parent and every right child is larger than its parent.

• A node with no children is called a leaf.
• The height of the tree is typically defined the number of levels below the root.² E.g., an empty tree has a height of -1, a tree with just one element has a height of 0, and tree with a root and one child has a height of 1.
• A tree is said to be full if all nodes have either two children or no children.
• A tree is said to be perfect if for every level except the bottom level, every node has two children.
• A tree is said to be complete if every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
• There are various definitions for a balanced tree.³
  • Some say that in order for a tree to be balanced the distance from the root to any leaf in the tree must differ by no more than one.
  • A looser definition is also acceptable: A balanced tree is one in which the distance from the root to any leaf differs by no more than a fixed constant multiple. Often this multiple is two, implying that the longest distance from root to leaf may be no more than two times the shortest distance from root to leaf.