Tree Basics

Up to this point, the data structures that we have considered have been linear -- they have modeled data as being in a sequence. However, there can be non-linear relationships in data as well -- for example, some relationships in data are hierarchical.

Examples of hierarchical relationships include:

• Managers and employees in an organization
• Ancestors and descendants in a family tree
• Directories and files in filesystems

Hierarchical data can be represented using a tree. Watch the following video to learn about trees as a data structure:

To summarize:

• Trees are (typically) linked data structures composed of nodes and edges (also known as links).
• At the "top" of the tree, there is a root node.
• Each node has zero or more child nodes. Nodes that don't have any children are leaf nodes. Nodes that have at least one child are interior nodes.
• Each node (except for the root) has a parent node.
• Trees are naturally recursive data structures. Each tree is a root node connected to subtrees starting from the root node's children.
• The depth of a node is the number of links on the path from the root to the node. The height of a tree is the maximum depth among all nodes.
• A common type of tree is a binary tree, in which nodes have two child pointers to left and right children.