Software Engineer's Notes

A binary tree is a hierarchical data structure where each node has at most two children. It’s great for ordered data, fast lookups/insertions (often near O(log n)), and in-order traversal. With balancing (AVL/Red-Black), performance becomes reliably logarithmic. Downsides include pointer overhead and potential O(n) worst-cases if unbalanced.

What Is a Binary Tree?

A binary tree is a collection of nodes where:

• Each node stores a value.
• Each node has up to two child references: left and right.
• The top node is the root; leaf nodes have no children.

Common variants

• Binary Search Tree (BST): Left subtree values < node < right subtree values (enables ordered operations).
• Balanced BSTs: (e.g., AVL, Red-Black) keep height ≈ O(log n) for consistent performance.
• Heap (Binary Heap): Complete tree with heap property (parent ≤/≥ children); optimized for min/max retrieval, not for sorted in-order traversals.
• Full/Complete/Perfect Trees: Structural constraints that affect height and storage patterns.

Key terms

• Height (h): Longest path from root to a leaf.
• Depth: Distance from root to a node.
• Subtree: A tree formed by a node and its descendants.

When Do We Need It?

Use a binary tree when you need:

• Ordered data with frequent inserts/lookups (BSTs).
• Sorted iteration via in-order traversal without extra sorting.
• Priority access (heaps for schedulers, caches, and task queues).
• Range queries (e.g., “all keys between A and M”) more naturally than in hash maps.
• Memory-efficient dynamic structure that grows/shrinks without contiguous arrays.

Avoid it when:

• You only need exact-key lookups with no ordering → Hash tables may be simpler/faster on average.
• Data is largely sequential/indexed → Arrays/ArrayLists can be better.

Real-World Example

Autocomplete suggestions (by prefix):

1. Store words in a BST keyed by the word itself (or a custom key like (prefix, word)).
2. To suggest completions for prefix “em”, find the lower_bound (“em…”) node, then do in-order traversal while keys start with “em”.
3. This provides sorted suggestions with efficient insertions as vocabulary evolves.
   (If extreme scale/branching is needed, a trie may be even better—but BSTs are a simple, familiar starting point.)

Another quick one: Task scheduling with a min-heap (a binary heap). The smallest deadline pops first in O(log n), ideal for job schedulers.

Main Operations & Complexity

On a (possibly unbalanced) Binary Search Tree

Operation	Average Time	Worst Time	Space (extra)
Search (find key)	O(log n)	O(n)	O(1) iterative; O(h) recursive
Insert	O(log n)	O(n)	O(1) / O(h)
Delete	O(log n)	O(n)	O(1) / O(h)
In-order/Preorder/Postorder Traversal	O(n)	O(n)	O(h)
Level-order (BFS)	O(n)	O(n)	O(w) (w = max width)

• n = number of nodes, h = height of the tree (worst n−1), w = max nodes at any level.
• A balanced BST keeps h ≈ log₂n, making search/insert/delete reliably O(log n).

On a Binary Heap

Operation	Time
Push/Insert	O(log n)
Pop Min/Max	O(log n)
Peek Min/Max	O(1)
Build-heap (from array)	O(n)

Space for the tree overall is O(n). Traversals use O(h) stack space recursively (or O(1) if done iteratively with your own stack/queue memory accounted as O(n) in BFS).

Core Operations Explained (BST)

• Search: Compare key at node; go left if smaller, right if larger; stop when equal or null.
• Insert: Search where the key would be; attach a new node there.
• Delete:
  • Leaf: remove directly.
  • One child: bypass node (link parent → child).
  • Two children: replace value with in-order successor (smallest in right subtree), then delete that successor node.
• Traversal:
  • In-order (LNR): yields keys in sorted order.
  • Preorder (NLR): useful for serialization/cloning.
  • Postorder (LRN): useful for deletions/freeing.

Advantages

• Near-logarithmic performance for search/insert/delete with balancing.
• Maintains order → easy sorted iteration and range queries.
• Flexible structure → no need for contiguous memory; easy to grow/shrink.
• Rich ecosystem → balanced variants (AVL, Red-Black), heaps, treaps, etc.

Disadvantages

• Unbalanced worst-case can degrade to O(n) (e.g., inserting sorted data into a naive BST).
• Pointer overhead per node (vs. compact arrays).
• More complex deletes than arrays/lists or hash maps.
• Cache-unfriendly due to pointer chasing (vs. contiguous arrays/heaps).

Practical Tips

• If you need reliably fast operations, choose a self-balancing BST (AVL or Red-Black).
• For priority queues, use a binary heap (typically array-backed, cache-friendlier).
• For prefix/string-heavy tasks, consider a trie; for exact lookups without ordering, consider a hash map.
• Watch out for recursion depth with very deep trees; consider iterative traversals.

Summary

Binary trees sit at the heart of many performant data structures. Use them when ordering matters, when you want predictable performance (with balancing), and when sorted traversals or range queries are common. Pick the specific variant—BST, balanced BST, or heap—based on your dominant operations.