Tree
A tree is a hierarchical, non-linear data structure consisting of nodes connected by edges, with one node designated as the root and every other node having exactly one parent, forming no cycles. Trees are used to represent hierarchical…
Definition
A tree is a hierarchical, non-linear data structure consisting of nodes connected by edges, with one node designated as the root and every other node having exactly one parent, forming no cycles. Trees are used to represent hierarchical relationships and support efficient search, insertion, and traversal operations, with common variants including binary trees, binary search trees, heaps, and balanced trees like AVL and red-black trees.
Overview
A tree generalizes the idea of a linked list into a branching hierarchy: each node can have zero or more children, and the structure has no cycles, meaning there is exactly one path between the root and any given node. Depth refers to a node's distance from the root; height refers to the longest path from a node to a leaf. Terminology includes parent, child, sibling, leaf (a node with no children), and subtree (any node and its descendants). Binary trees restrict each node to at most two children, commonly labeled left and right. A binary search tree (BST) further orders nodes so that a node's left subtree contains only smaller values and its right subtree only larger ones, enabling O(log n) average-case search, insert, and delete — though this degrades to O(n) in the worst case for an unbalanced tree (e.g., inserting sorted data). Self-balancing variants like AVL trees and red-black trees maintain logarithmic height through rotations, guaranteeing O(log n) worst-case operations. Traversal strategies define the order nodes are visited: in-order (left, node, right) yields sorted output for a BST, pre-order (node, left, right) is useful for copying a tree, and post-order (left, right, node) is useful for deletion. Breadth-first (level-order) traversal visits nodes level by level using a queue, while the depth-first variants typically use recursion or an explicit stack. Trees underpin many real systems: file systems and DOM structures are trees, database indexes commonly use B-trees or B+ trees for disk-efficient lookups, and heaps (a specialized tree) implement priority queues.
Key Concepts
- Hierarchical structure: one root, no cycles, each node has one parent
- Binary trees restrict nodes to at most two children
- Binary search trees maintain ordering for O(log n) average search
- Self-balancing variants (AVL, red-black) guarantee logarithmic height
- Traversal orders: in-order, pre-order, post-order, and level-order
- B-trees and B+ trees optimize for disk-based database indexing
- Used to model hierarchical data: file systems, DOM, org charts