Trees

A tree is a hierarchical form of data structure. Data structures such as lists, queues, and stacks are linear in that the items are stored in a sequential way. However, a tree is a non-linear data structure, as there is a parent-child relationship between the items. The top of the tree’s data structure is known as a root node. This is the ancestor of all other nodes in the tree.

Tree data structures are very important, owing to their use in various applications, such as parsing expressions, efficient searches, and priority queues. Certain document types, such as XML and HTML, can also be represented in a tree.

In this chapter, we will cover the following topics:

• Terms and definitions of trees
• Binary trees and binary search trees
• Tree traversal
• Binary search trees