Trees and Binary Search Trees Cheat Sheet

Updated 2026-04-29

Next Topic: Twelve-Factor App Methodology Cheat Sheet

🧠Study flashcards on this topic93 cards · spaced repetition→

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, 93 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Core Tree TerminologyTable 2: Binary Tree TypesTable 3: Binary Search Tree (BST) FundamentalsTable 4: BST Core OperationsTable 5: Tree Traversal MethodsTable 6: Depth-First vs Breadth-First SearchTable 7: Advanced Traversal PatternsTable 8: Self-Balancing BST TypesTable 9: AVL Tree RotationsTable 10: Specialized Tree StructuresTable 11: Common Tree AlgorithmsTable 12: BST Complexity AnalysisTable 13: Advanced BST OperationsTable 14: Tree Properties and FormulasTable 15: Tree Problem-Solving Patterns

Quick IndexSubscribe to unlock

A jump-to index of every table row in this cheat sheet.

Mind MapSubscribe to unlock

An interactive map of every table and concept in this topic.

Table 1: Core Tree Terminology

Before reasoning about any tree algorithm you need a shared vocabulary, and these terms are it — root, leaf, height, depth, and the rest. Get the difference between height and depth straight here (one counts down toward leaves, the other counts up from the root) and most later confusion disappears.

Term	Example	Description
Root	`root = TreeNode(10)`	• The topmost node with no parent • serves as the single entry point for all tree operations.
Leaf (External Node)	`node.left == None and node.right == None`	• A node with no children • appears at the tree's periphery and marks endpoints in traversals.
Internal Node	Any node with at least one child	• A node with one or two children • forms the structural backbone connecting root to leaves.
Height	`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	Depth of root is 0	• Number of edges from the root to a specific node • increases by 1 at each level downward.
Level	Root is at level 0	• The set of all nodes at the same depth • level-order traversals process one level at a time.
Edge	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.
Subtree	`subtree = node.left`	• A node and all its descendants • every non-leaf node is the root of a left and right subtree.
Path	Root → child → grandchild	• A sequence of nodes connected by edges between two nodes • path length = number of edges traversed.
Degree	Binary tree nodes have degree ≤ 2	• The number of children a node has • binary trees restrict degree to a maximum of 2.
Ancestor	All nodes on path from root to node	• Any node on the path from root to a given node • used in lowest common ancestor (LCA) queries.
Descendant	All nodes in node's subtree	• Any node reachable by moving downward through children • the opposite relationship of ancestor.
Sibling	Nodes sharing the same parent	• Two nodes with the same parent node • left and right children are always siblings of each other.

Table 2: Binary Tree Types

Not every binary tree is shaped the same, and the shape decides what guarantees you get. These classifications — complete, perfect, full, balanced, and the pathological degenerate case — describe how densely a tree is packed, which is exactly what determines whether operations stay logarithmic or collapse to linear.

Type	Example	Description
Complete Binary Tree	Heap data structures	• All levels fully filled except possibly the last, which fills left to right • guarantees $O(\log n)$ height.

The rest of this section is part of the full cheat sheet

Table 3: Binary Search Tree (BST) Fundamentals

The single ordering rule — everything left is smaller, everything right is larger — is what turns an ordinary binary tree into a searchable structure. These properties show what falls out of that invariant for free: sorted output from an inorder walk, the minimum sitting at the far left, the maximum at the far right, and the one detail people forget, that duplicates have no defined home until you pick a strategy.

Property	Example	Description
BST Property	`node.left.val < node.val < node.right.val`	• Left subtree contains only smaller values, right subtree only larger • this ordering enables efficient search, insert, and delete.

The rest of this section is part of the full cheat sheet

Table 4: BST Core Operations

Insert and search are the easy half — you just compare and walk down. Deletion is where the real work lives, splitting into three cases by how many children the doomed node has, with the two-child case forcing you to swap in an inorder successor or predecessor. That "next/previous in sorted order" idea is worth internalizing, because it reappears all over BST problems.

Operation	Example	Description
Insert	`if val < node.val: insert_left(val)` `else: insert_right(val)`	• Compare value with current node and recurse left/right • insert as leaf at correct position maintaining BST property • $O(h)$ time.

The rest of this section is part of the full cheat sheet

Table 1: Core Tree Terminology

Term	Example	Description
Root	`root = TreeNode(10)`	• The topmost node with no parent • serves as the single entry point for all tree operations.
Leaf (External Node)	`node.left == None and node.right == None`	• A node with no children • appears at the tree's periphery and marks endpoints in traversals.
Internal Node	Any node with at least one child	• A node with one or two children • forms the structural backbone connecting root to leaves.
Height	`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	Depth of root is 0	• Number of edges from the root to a specific node • increases by 1 at each level downward.
Level	Root is at level 0	• The set of all nodes at the same depth • level-order traversals process one level at a time.
Edge	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.
Subtree	`subtree = node.left`	• A node and all its descendants • every non-leaf node is the root of a left and right subtree.
Path	Root → child → grandchild	• A sequence of nodes connected by edges between two nodes • path length = number of edges traversed.
Degree	Binary tree nodes have degree ≤ 2	• The number of children a node has • binary trees restrict degree to a maximum of 2.
Ancestor	All nodes on path from root to node	• Any node on the path from root to a given node • used in lowest common ancestor (LCA) queries.
Descendant	All nodes in node's subtree	• Any node reachable by moving downward through children • the opposite relationship of ancestor.
Sibling	Nodes sharing the same parent	• Two nodes with the same parent node • left and right children are always siblings of each other.

Table 2: Binary Tree Types

Type	Example	Description
Complete Binary Tree	Heap data structures	• All levels fully filled except possibly the last, which fills left to right • guarantees $O(\log n)$ height.

Table 3: Binary Search Tree (BST) Fundamentals

Property	Example	Description
BST Property	`node.left.val < node.val < node.right.val`	• Left subtree contains only smaller values, right subtree only larger • this ordering enables efficient search, insert, and delete.

Table 4: BST Core Operations

Operation	Example	Description
Insert	`if val < node.val: insert_left(val)` `else: insert_right(val)`	• Compare value with current node and recurse left/right • insert as leaf at correct position maintaining BST property • $O(h)$ time.

Trees & Binary Search Trees Cheat Sheet

Table 1: Core Tree Terminology

Table 2: Binary Tree Types

Table 3: Binary Search Tree (BST) Fundamentals

Table 4: BST Core Operations

Trees & Binary Search Trees Cheat Sheet

Table 1: Core Tree Terminology

Table 2: Binary Tree Types

Table 3: Binary Search Tree (BST) Fundamentals

Table 4: BST Core Operations