Binary Search Tree 
Last Updated:
11/12/2013 
Binary Search Tree Representation
Here is an array containing 7 integers sorted in nondecreasing 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 log_{2} (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) = 2^{x},
where x = the level number
So at level = zero, there are 2^{0} = 1 nodes, and at 2^{1} = 2 nodes maximum, and at 2^{2} = 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 nonempty tree is represented as a 3tuple:
 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 3tuple (representing the nonempty left subtree)
 the 3rd value in the tuple represents the right subtree.
Abstract Tree t 
SemiAbstract 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)))
