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:

binary search tree

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:

 

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