Mastering Algorithms with C

Chapter 9. Trees

Picture a family tree, the draw sheet of a tournament, or the roots of a plant; these are all good examples of a tree’s organization as a data structure. In computing, a tree consists of elements called nodes organized in a hierarchical arrangement. The node at the top of the hierarchy is called the root . The nodes directly below the root are its children , which in turn usually have children of their own. With the exception of the root, each node in the hierarchy has exactly one parent, which is the node directly above it. The number of children a node may parent depends on the type of tree. This number is a tree’s branching factor, which dictates how fast the tree will branch out as nodes are inserted. This chapter focuses on the binary tree, a relatively simple but powerful tree with a branching factor of 2. It also explores binary search trees, binary trees organized specifically for searching.

This chapter covers:

Binary trees

Trees containing nodes with up to two children. The binary tree is a very popular type of tree utilized in a wide variety of problems. It provides the foundation for more sophisticated tree structures as well.

Traversal methods

Techniques for visiting the nodes of a tree in a specific order. Because the nodes of a tree are organized in a hierarchical fashion, there are several options for traversing them.

Tree balancing

A process used to keep a tree as short as possible for a given number of nodes. This is especially important in search ...