Trees and Binary Search Trees are hierarchical data structures fundamental to computer science, storing data in parent-child relationships rather than linear sequences. While a binary tree simply restricts each node to at most two children, a Binary Search Tree (BST) imposes an ordering constraint — left children hold smaller values, right children hold larger values — enabling logarithmic-time operations when balanced. Understanding traversal patterns, balancing mechanisms, and structural properties is essential for efficient searching, sorting, and hierarchical data manipulation across countless algorithms and applications.
What This Cheat Sheet Covers
This topic spans 15 focused tables and 105 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
Table 1: Core Tree Terminology
| Term | Example | Description |
|---|---|---|
root = TreeNode(10) | • The topmost node with no parent • serves as the single entry point for all tree operations. | |
node.left == None and node.right == None | • A node with no children • appears at the tree's periphery and marks endpoints in traversals. | |
Any node with at least one child | • A node with one or two children • forms the structural backbone connecting root to leaves. | |
height = max(left_height, right_height) + 1 | • Number of edges on the longest path from a node to any descendant leaf • the root's height equals the tree's height. | |
Depth of root is 0 | • Number of edges from the root to a specific node • increases by 1 at each level downward. | |
Root is at level 0 | • The set of all nodes at the same depth • level-order traversals process one level at a time. | |
Connection between parent and child | • The link between two nodes representing a parent-child relationship • a tree with n nodes has exactly n-1 edges. |