Tree Data Structure
A tree is a hierarchical, non-linear data structure made up of nodes connected by edges. Unlike arrays or linked lists, which store data in a sequential or...
What Is a Tree and Why It Matters
A tree is a hierarchical, non-linear data structure made up of nodes connected by edges. Unlike arrays or linked lists, which store data in a sequential order, a tree organizes data in a parent-child relationship. Every tree has exactly one root node, which is the topmost node with no parent. Every other node in the tree has exactly one parent and zero or more children. Nodes with no children are called leaves, and nodes between the root and leaves are called internal nodes.
The depth of a node is the number of edges from the root to that node. The height of a tree is the maximum depth among all its nodes. The subtree rooted at a node consists of that node and all its descendants. Trees are useful whenever data has a natural hierarchical structure — file systems, organization charts, XML or HTML documents, and game decision trees all map naturally to this model.
Consider a family tree where the grandparent is the root, their children are the second level, and grandchildren form the leaves. Representing this in a tree structure makes it easy to answer questions such as "who are all the descendants of node X?" simply by traversing the subtree at X, rather than scanning every record in a flat list.
Key Terminology and Structural Properties
Understanding the vocabulary around trees is essential before studying any specialized variant. The degree of a node is the number of its children. A node with degree zero is a leaf. A path is a sequence of nodes where each consecutive pair is connected by an edge. A tree with N nodes always has exactly N minus one edges — a property that distinguishes trees from general graphs, which may have cycles.
A forest is a collection of disjoint trees. Removing the root of a tree produces a forest of subtrees. Ordered trees treat the left-to-right arrangement of children as significant, while unordered trees do not. In many programming problems, trees are ordered and binary, meaning each node has at most two children conventionally called left and right.
The height of a balanced tree with N nodes is approximately log base 2 of N, which is why tree-based operations can be dramatically faster than linear structures for large datasets.
Representing Trees in Code and Interview Tips
The most common way to represent a tree node in code is a struct or class containing a value and pointers to children. For a generic tree, children may be stored in an array or linked list. For a binary tree, two pointers named left and right are conventional.
A simple node definition looks like: Node { value, left, right }. You allocate a root node, then attach children by setting the pointer fields. Alternatively, trees can be stored implicitly in an array: for a node at index i, its left child is at 2i plus one and its right child is at 2i plus two. This array representation avoids pointer overhead and is used extensively in heap implementations.
Space complexity for a tree of N nodes is O(N) regardless of representation. Worked example: given a file system where each directory can have multiple subdirectories, model it as a tree where each directory node stores its name and a list of child nodes. Listing all files under a directory becomes a depth-first traversal of the subtree at that node.
Interview tip: when asked to design any system with hierarchical relationships, immediately propose a tree structure and justify it by explaining how parent-child traversal reduces lookup time compared to flat storage.