Binary Search Tree 
Last Updated:
11/12/2013 
Binary Search Tree Representation
Here is an array containing 15 integers sorted in nondecreasing order:
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
1 
5 
9 
12 
15 
21 
29 
31 
35 
37 
52 
77 
90 
93 
94 
The following is the Binary Search Tree representation of the sorted array
from the previous section:
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, 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 = left + right + 1 (for the
root).

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.

subtree  a binary tree whose root is the child of another node.

root node  is a node in a binary tree that has no parent.

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.

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.

leaf node  a node that has no children. Also known as a frontier
node.

interior node  a node that has children.

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

height of T  if T is empty, then height (T) = 0.
Otherwise, height (T) = 1 + maximum (height (T.left), height (T.right)).

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.

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.