Lecture Notes for Computer Algorithms I

2 December 2003 - A Binary Tree ADT

1. More terms.

   1. A path through a binary tree is a sequence of edge traversals through the tree.

      1. Usually starting at the root, but not necessarily.

      2. Usually obeying the edge direction, but not necessarily.

   2. The length of a path (or just path length or just length) is the number of nodes in the path.

      1. This could be one for a path that doesn't go anywhere.

      2. Sometimes length refers to the number of edges instead.

         1. This can result in off-by-one errors.

   3. A binary tree's height is the length of the longest path starting at the root.

      1. This is sometimes called the tree's depth too.

2. The interface.

   1. The usual suspects add(), remove(), find(), and empty().

   2. Traversal functions are also useful: left_child() and right_child().

3. The implementation.

   1. We can exploit the equivalence between binary trees and linked lists.

      1. But now binary trees are no better than linked lists, which misses the point.

This page last modified on 3 December 2003.