Binary Trees - Data Structures and Algorithm Analysis - page 154

5.3 Binary Tree Node Implementations

In this section we examine ways to implement binary tree nodes. We begin with
some options for pointer-based binary tree node implementations. Then comes a
discussion on techniques for determining the space requirements for a given imple-
mentation. The section concludes with an introduction to the array-based imple-
mentation for complete binary trees.

5.3.1 Pointer-Based Node Implementations

By definition, all binary tree nodes have two children, though one or both children
can be empty. Binary tree nodes typically contain a value field, with the type of
the field depending on the application. The most common node implementation
includes a value field and pointers to the two children.
Figure 5.7 shows a simple implementation for the BinNode abstract class,
which we will name BSTNode . Class BSTNode includes a data member of type
E , (which is the second generic parameter) for the element type. To support search
structures such as the Binary Search Tree, an additional field is included, with
corresponding access methods, to store a key value (whose purpose is explained
in Section 4.4). Its type is determined by the first generic parameter, named Key .
Every BSTNode object also has two pointers, one to its left child and another to its
right child. Figure 5.8 illustrates the BSTNode implementation.
Some programmers find it convenient to add a pointer to the node's parent,
allowing easy upward movement in the tree. Using a parent pointer is somewhat
analogous to adding a link to the previous node in a doubly linked list. In practice,
the parent pointer is almost always unnecessary and adds to the space overhead for
the tree implementation. It is not just a problem that parent pointers take space.
More importantly, many uses of the parent pointer are driven by improper under-
standing of recursion and so indicate poor programming. If you are inclined toward
using a parent pointer, consider if there is a more efficient implementation possible.
An important decision in the design of a pointer-based node implementation
is whether the same class definition will be used for leaves and internal nodes.
Using the same class for both will simplify the implementation, but might be an
inefficient use of space. Some applications require data values only for the leaves.
Other applications require one type of value for the leaves and another for the in-
ternal nodes. Examples include the binary trie of Section 13.1, the PR quadtree of
Section 13.3, the Huffman coding tree of Section 5.6, and the expression tree illus-
trated by Figure 5.9. By definition, only internal nodes have non-empty children.
If we use the same node implementation for both internal and leaf nodes, then both
must store the child pointers. But it seems wasteful to store child pointers in the
leaf nodes. Thus, there are many reasons why it can save space to have separate
implementations for internal and leaf nodes.