Tree Data Structures

A tree is a connected graph with no cycles, so there is exactly one simple path between any two nodes. In a rooted tree, one node is designated as the root, and every other node has exactly one parent. Nodes can have children; nodes without children are leaves. A node's depth is its distance from the root, and the tree's height is the greatest such distance. These properties make trees useful for representing product categories, nested documents, directory hierarchies, and relationships between organizational units.

The defining structure matters when choosing a data model. A category hierarchy in which each category has one parent can be a tree. If a category belongs to multiple parents, the relationship is no longer a tree; it may be a directed acyclic graph. If relationships can lead back to an ancestor, cycles are present and graph-processing techniques are needed. During ingestion, validate parent identifiers, reject unintended cycles, and check for missing parents. Multiple disconnected hierarchies form a forest rather than one tree.

Traversal determines how an algorithm visits nodes. Depth-first search follows a branch before exploring its siblings and is useful for recursively transforming nested JSON or calculating totals from descendants. Preorder processes a parent before its children, while postorder processes children before their parent, making postorder appropriate for bottom-up aggregation. Breadth-first search uses a queue to visit nodes level by level, which is useful when finding the nearest matching descendant. A complete traversal takes O(n) time for n nodes. Breadth-first traversal can require substantial memory for wide levels, while recursive depth-first traversal can exhaust the call stack on very deep input.

Tree shape also affects search performance. A binary search tree maintains an ordering relationship between each node and its subtrees; it is not merely any tree with at most two children. Balanced search trees support lookup, insertion, and deletion in O(log n) time, but an unbalanced binary search tree can degrade to O(n). Inorder traversal of a binary search tree produces keys in sorted order. A heap instead maintains a priority relationship and does not provide the same efficient arbitrary-key lookup. B-trees and related structures use high branching factors to reduce page accesses in database indexes.

In cloud data pipelines, an ingestion job might receive nested orders containing line items and adjustments. A transformation can walk the document tree, preserve order identifiers, and emit relational rows. The engineer must define how arrays expand: independently flattening two sibling arrays and joining them incorrectly can multiply rows. For hierarchy records stored as identifiers and parent identifiers, build an adjacency mapping before traversal to avoid repeatedly scanning the entire input for each node.

Practical trade-offs extend beyond algorithmic complexity. Database indexes consume storage and increase write work, while distributed tree processing can incur network requests and uneven workloads. Keep related nodes together when possible, batch remote reads, and use explicit stacks or depth limits for untrusted input. Do not assume that a logical hierarchy implies a physical tree implementation: object-storage key prefixes can resemble folders without providing a traditional filesystem tree. For exam questions, distinguish trees from general graphs, match traversal order to the required result, and evaluate complexity using the actual tree shape rather than assuming every tree is balanced.