Binary Search Tree
Binary Search Tree Representation
Here is an array containing 15 integers sorted in non-decreasing order:
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 log2 (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
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
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
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
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
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) = 2x,
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
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.