Module 7: Tree Data Structure
A tree is a nonlinear data structure made of vertices and edges. It is commonly used to represent hierarchy, such as folders, organization charts, decision processes, and search structures.
A tree has a starting node called the root. From the root, other nodes branch downward.
Important Tree Terms
| Term | Meaning |
|---|---|
| Vertex / node | A data item in the tree. |
| Edge | A connection between two nodes. |
| Path | A sequence of connected nodes. |
| Root | The top node of the tree. |
| Parent | A node directly above another node. |
| Child | A node directly below another node. |
| Leaf / terminal node | A node with no children. |
| Nonterminal / internal node | A node with at least one child. |
| Subtree | A smaller tree formed by a node and its descendants. |
| Forest | A set of separate trees. |
| Level | A node's distance from the root. |
| Height | The largest level in the tree. |
| Path length | The sum of node levels in a tree. |
Binary Tree
A binary tree is a tree where each node can have at most two children: a left child and a right child.
Binary trees are useful because they combine some advantages of arrays and linked lists. In certain forms, such as binary search trees, searching can be faster than scanning a list, while insertion and deletion can remain flexible.
Diagram Description
A tree diagram usually shows the root at the top, with edges connecting it to lower nodes. Leaves appear at the bottom or at endpoints of branches.
Example summary for a tree made from the letters of COMPUTERS:
Vertices: C, O, M, P, U, T, E, R, S
Root: U
Leaf nodes: C, P, T, S
Internal nodes: U, M, E, O, R
Activity 10: Build a Complete Binary Tree
ProReviewer — locked
Drills, code labs, and full solutions.