Data Structures and Algorithms
Unbalanced Trees

If items are added to a binary tree in order then the following unbalanced tree results:

. The worst case search of this tree may require up to n comparisons. Thus a binary tree's worst case searching time is O(n). Later, we will look at red-black trees, which provide us with a strategy for avoiding this pathological behaviour.

Key terms

Balanced Binary Tree
Binary tree in which each leaf is the same distance from the root.

Back to Trees
Back to the Table of Contents
© John Morris, 1998