Binary Search Tree

Last Updated: 11/12/2013


Binary Search Tree Representation

Here is an array containing 15 integers sorted in non-decreasing 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 log2 (N) probes of the tree, where N = number of nodes in the tree.

Here are some tree facts and terminology:

 

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)))