Binary Search Tree Last Updated: 11/12/2013

### Binary Search Tree Representation

Here is an array containing 7 integers sorted in non-decreasing order:
0 1 2 3 4 5 6
8 21 31 35 37 49 52

The following is a Binary Search Tree representation of the sorted array from above:

Given the above representation, one can start at the root (labeled by the number 31), and find any value by performing only log2 (N) probes of the tree (assuming the tree is balanced), where N = number of nodes in the tree.

Here are some tree facts and terminology:

• labeled binary tree T
• T consists of n nodes, n >= 0.
• If n = 0, then T is EMPTY.
• If n > 0, then T consists of a root node r and two binary trees, left and right. Such that n = |T.left| + |T.right| + 1 (for the root).
In the tree pictured above, the T rooted at 31 size is 7, 1 (for the root) + 2 (size of T.left) + 4 (size of T.right)
• The binary tree is labeled because a value is associated with each node in the tree.
• child node & parent node - Let T be a binary tree with root u, and let v be any node in T. If v is either the root of the left subtree, or the root of the right subtree, then v is called the child of u, and u is called the parent of v.
In the tree above, the node labeled with 37 is a child of 31 and a parent of both 35 and 52.
• subtree - a binary tree whose root is the child of another node.
The two subtrees of the node labeled 31 (i.e., the root node of the entire tree) are the trees rooted at 21 and 37.
• root node - is a node in a binary tree that has no parent.
Node 31 (in the tree above) has no parent so it is the root of the tree.
• descendant - Let T be binary tree of n nodes, n >= 1, and let u and v be two nodes in T. v is a descendant of u, if v is a child of some node w, where w is a descendant of u.
• ancestor - Let T be binary tree of n nodes, n >= 1, and let u and v be two nodes in T. u is a ancestor of v, if u is a parent of some node w, where w is a ancestor of v.
The root node labeled with 31 is an ancestor of all the other nodes in the tree. However, the node labeled 37 is the ancestor of only the following nodes: 35, 49, and 52.
• sibling node - Let T be a binary tree with root u and a left subtree with root u, and a right subtree with root v, then u and v are siblings.
Nodes 21 and 37 are siblings in the tree shown above.
• leaf node - a node that has no children. Also known as a frontier node.
In the tree above, nodes labeled with 8, 35, and 49 are all leaf nodes.
• interior node - a node that has children.
In the tree above, nodes labled with 21, 31, 37, and 52 are all interior nodes.
• level of a node - to determine the level of a node in tree T, number the root of T at level 0, and then label every other node in T by giving it one more than the level of its parent.
• maximum number of nodes possible at a particular level - maxNodesPossible(x) = 2x, where x = the level number
So at level = zero, there are 20 = 1 nodes, and at 21 = 2 nodes maximum, and at 22 = 4 nodes maximum, and so on.
• height of T - if T is empty, then height (T) = 0.
Otherwise, height (T) = 1 + maximum (height (T.left), height (T.right)).
In the tree above, the tree rooted at 37 has height 3 because its left subtree has height = 1, and its right subtree has height = 2, the maxiumum between the two subtrees is 2, so the height of the tree rooted at 37 is 1 plus 2 = 3.
• skinny tree - a tree T where each internal node has at most one internal child.
• balanced tree - a tree where at every node, the heights of the left and right subtrees must not differ by more than 1.
The tree shown above, is balanced because between every two sibling subtrees in the entire tree, the difference between the height of the left subtree and the right subtree is 1 or less.
• search tree - is a property that the value associated with a node is larger than the value associated with any node in its left subtree and smaller than the value associated with any node in its right subtree.
• list of lists abstract representation: the tree show above can be represented abstractly as a recursively defined list of lists.
• t = (31 (21 (8 E E) E) (37 (35 E E) (52 (49 E E) E)))
• Empty trees are represented with the letter "E". This is the base case for a recursively defined binary tree data structure.
• Each non-empty tree is represented as a 3-tuple:
• the 1st value in the tuple is the label of node at the tree's root
• the 2nd value in the tuple represents the left subtree, is either E (for an empty left subtree), or itself a 3-tuple (representing the non-empty left subtree)
• the 3rd value in the tuple represents the right subtree.

 Abstract Tree t Semi-Abstract Tree t Raw Nodes & Pointers Tree t t = (31 (21 E E) (37 (35 E E) (52 E E))) t = (31 (21 E E) (37 (35 E E) (52 E E))) t = (31 (21 E E) (37 (35 E E) (52 E E)))