Binary Search Tree

Binary Search Tree
Originally uploaded by USUDave.

CS 5050: Advanced Algorithms
January 2007

We had to draw a Binary Search Tree of height=7. I thought "I Can't Fit That Onto A Piece of Paper Neatly.... I Need A Bigger Canvas....Hrm..."

I drew this on the sidewalk on campus, took digital photos of it, and then turned those photos for my homework. Dr. Yan Really liked it. :-)

More Photos

Theorem: Let T be a (proper) binary tree with n nodes, and let h denote the height of T. Then T has the following properties:

1. The number of external nodes in T is at least h+1 and at most 2^h .

2. The number of internal nodes in T is at leasat h and at most 2^h - 1.

3. The total number of nodes in T is at leasat 2h + 1 and at most 2^(h+1).

4. The height of T is at least log(n+1)-1 and at most (n-1)/2, that is, log(n+1)-1 < h <(n-1)/2.

That Means that this binary tree has

• 128 leaves
• 127 Internal Nodes
• 255 Total Nodes