Data Structures and Algorithms: BRIDGES

Frequently, we have the need to traverse a binary tree and perform a specific action on each node, such as printing its contents. This process of visiting all the nodes in a specific order is known as a traversal. An enumeration of the tree’s nodes is a traversal that lists every node exactly once. In certain applications, the order in which nodes are visited may not matter as long as each node is visited only once. However, for other applications, it is crucial to visit the nodes in an order that preserves a specific relationship.

For example, we might wish to make sure that we visit any given node before we visit its children. This is called a preorder traversal.

In some cases, we may want to visit each node in a binary tree only after visiting its children and their subtrees. This is necessary, for example, when we want to free up memory by deleting all nodes in the tree. We need to delete the children of a node before deleting the node itself. However, to do this, we must first delete the children’s children, and so on. This type of traversal, where we visit the children nodes first and then the parent node, is known as a postorder traversal.

An inorder traversal first visits the left child (including its entire subtree), then visits the node, and finally visits the right child (including its entire subtree). The binary search tree makes use of this traversal to print all nodes in ascending order of value.

Next, we will explore different implementations for tree traversals. However, before we proceed, we need to define an Abstract Data Type (ADT) for binary tree nodes, which we will call BinNode. Similar to how a linked list consists of a collection of link objects, a tree is composed of a collection of node objects. The BinNode ADT provides member functions to set or retrieve the element value, obtain a pointer to the left child, retrieve a pointer to the right child, and determine if the node is a leaf. This class will be utilized in the subsequent binary tree structures that will be discussed.

Adding a parent pointer to a node can provide convenient upward movement within the tree, similar to adding a link to the previous node in a doubly linked list. However, in practice, the use of a parent pointer is often unnecessary and can increase the space overhead for the tree implementation. Moreover, relying heavily on the parent pointer can indicate a misunderstanding of recursion and result in poor programming practices. Before deciding to use a parent pointer, it’s essential to consider if there is a more efficient alternative.

In pointer-based node implementations, an important design decision is whether to use the same class definition for both leaf nodes and internal nodes. While using the same class simplifies the implementation, it may not be the most space-efficient approach. Some applications only require data values for the leaf nodes, while others need different types of values for internal and leaf nodes. It may seem wasteful to store child pointers in leaf nodes if they have no children. Thus, having distinct implementations for internal and leaf nodes can provide space optimization benefits.

Here is a link to the OpenDSA textbook that has examples for Preorder, Postorder, and Inorder traversals: Read Me¹