Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004
A tree’s root is at level 1, not level 0.
Proving that a binary tree is fully balanced if and only if it either is empty or both of its subtrees are fully balanced and have the same height. All occurrences of variable h in the third paragraph of the induction step should be H (i.e., the tree size for which the induction step is proving the proposition).
Copyright © 2004. Charles River Media. All rights reserved.
Revised Nov. 23, 2004