Trees

A tree is a hierarchical data structure made up of nodes connected by edges. Unlike linear structures such as arrays or linked lists—where elements are arranged one after another—trees organize data in parent-child relationships, forming a branching structure that mirrors how we naturally represent hierarchies.

Consider a company's organization chart, a file system on your computer, or the nested elements of an HTML document. Each of these is a tree: there is one top-level entry point, and every element belongs to exactly one position in the hierarchy.

Key Properties of Trees#

A tree must satisfy all of the following properties. If any of them is violated, the structure is no longer a tree—it may instead be a general graph, a forest (multiple disconnected trees), or contain a cycle.

Tree Terminology#

Tree terminology can feel abstract at first. The key is to anchor each term to a concrete position in the tree: where is the node relative to the root, and does it have children?

Two terms worth extra attention:

• Ancestors form the path from a node back up to the root. Every node you pass through while walking upward is an ancestor. The root is an ancestor of every node in the tree.
• Descendants are all nodes reachable by walking downward from a given node—its children, their children, and so on. Together with the node itself, they form a subtree.

Tree Properties: Height, Depth, and Level#

These three measurements describe the position and size of nodes within a tree. They are frequently confused with one another—especially height and depth—so it is worth being precise:

• Depth answers: "How far is this node from the root?" It is measured by counting edges going downward from the root. The root itself has depth 0.
• Height (of a node) answers: "How far down does this node's subtree extend?" It is measured by counting edges going upward from the deepest leaf in that subtree. A leaf node has height 0.
• Height (of a tree) is the height of the root node—equivalently, the number of edges on the longest root-to-leaf path.
• Level is another name for depth. A node at level 0 is the root, level 1 contains the root's children, and so on.

Convention note: Some implementations measure height by number of nodes on the path rather than number of edges. Under that convention, a single-node tree has height 1 instead of 0. Always verify which convention a codebase uses before comparing height values across functions.

Trees vs Linear Structures#

When choosing a data structure, consider whether your data has a natural hierarchy and what operations you perform most often. Trees offer significant performance advantages for search and hierarchical access, at the cost of higher memory usage and implementation complexity.

The O(log n) performance of balanced trees comes from the fact that each comparison eliminates roughly half of the remaining nodes—the same principle as binary search. However, this guarantee only holds when the tree remains balanced. An unbalanced tree can degrade to O(n) in the worst case, which is why self-balancing variants (AVL, Red-Black) exist.

Types of Trees#

Each tree variant is designed to make a specific set of operations fast. Understanding which type to use—and why—matters more for practical development than memorizing their implementation details.

Tree Traversal Concepts#

Traversing a tree means visiting every node exactly once in a defined order. The order you choose determines what information you can extract efficiently—for example, traversing a binary search tree in a specific order yields sorted output, while another order is ideal for copying or deleting the tree.

There are two fundamental strategies:

• Depth-First Search (DFS): Explore as far down one branch as possible before backtracking. Naturally implemented with recursion (using the call stack implicitly) or an explicit stack. DFS has three variants—preorder, inorder, and postorder—that differ only in when the current node is visited relative to its children.
• Breadth-First Search (BFS): Visit all nodes at the current level before moving to the next. Requires an explicit queue to track which nodes to process next.

The choice of data structure for each strategy follows from the algorithm's behavior: DFS must remember where to backtrack when it finishes a branch—a stack (last-in, first-out) handles this naturally. BFS must process nodes in the order they were discovered—a queue (first-in, first-out) ensures that all nodes at one level are visited before any node at the next level.

Common Applications of Trees#

Trees are used extensively throughout computer science and software engineering:

When to Use Trees#

Reviewing AI-Generated Code#

Tree algorithms involve recursive thinking, null pointer handling, and careful base-case design. These are precisely the areas where AI-generated code most often contains subtle errors. A function may look correct at a glance but silently produce wrong results on edge cases—empty trees, single-node trees, or trees that are heavily skewed to one side. Always trace through these cases manually before trusting AI output.

Questions to Ask When Reviewing Tree Code#

1. "What happens with an empty tree?" — The code must handle a null root without crashing.
2. "What happens at leaf nodes?" — Children are null (or an empty list) and must not be dereferenced.
3. "Is this calculating height or depth?" — Height goes up from leaves; depth goes down from root.
4. "What is the traversal order?" — Verify that the preorder, inorder, or postorder logic matches the intended behavior.
5. "Which height convention does this use?" — Confirm whether height is measured in edges (leaf = 0) or in nodes (leaf = 1), and check that it is consistent across all functions.

Summary#

Now that you understand tree fundamentals, you are ready to explore specific tree types. Continue with Binary Trees to learn about the most common tree structure and its traversal algorithms.