Tree Fundamentals & Binary Tree Varieties

Topics Covered:
63. Tree Terminology & Anatomy • 64. Fundamental Mathematical Tree Theorems • 65. Structural Classification of Trees • 66. Binary Tree Anatomy • 67. Complete Binary Tree • 68. Full (Strict) Binary Tree • 69. Perfect Binary Tree • 70. Balanced Trees • 71. Degenerate (Skewed) Tree

---

Trees represent computing's primary hierarchical abstraction, modeling nested relationships, recursive sub-problems, and logarithmic search boundaries across memory and storage systems. Unlike linear structures (arrays and linked lists) that enforce a single predecessor and successor, trees organize data through parent-child hierarchies that balance storage flexibility with efficient multi-way branching. Understanding tree topology, topological invariants, node degrees, and structural tree varieties forms the prerequisite for mastering self-balancing search trees, spatial indices, and heap architectures.

• Formulate the graph-theoretic definition of a rooted tree and verify the edge-vertex invariant $|E|=|V|-1$.
• Distinguish between node depth, node height, subtree height, and tree diameter across hierarchical structures.
• Prove the Full Binary Tree theorem relating leaf count to internal node count ($L=I+1$).
• Differentiate the 5 canonical binary tree varieties: Full, Complete, Perfect, Balanced, and Degenerate (Skewed).
• Implement zero-pointer array mapping for Complete Binary Trees via arithmetic child/parent indexing ($2i+1,2i+2,\lfloor (i-1)/2\rfloor$).

---

Formally, a Tree $T=(V,E)$ is an undirected, connected, acyclic graph. When directed away from a distinguished origin, it is called a Rooted Directed Tree, defined by three invariant properties:

1. Unique Root: There exists exactly one node $r\in V$ with in-degree ${\text{deg}}^{-}(r)=0$.
2. Single Predecessor: Every other node $u\in V\setminus \{r\}$ has an in-degree of strictly ${\text{deg}}^{-}(u)=1$ (exactly one parent).
3. Acyclic Connectivity: For every node $u\in V$, there exists a unique simple directed path from root $r$ to $u$.

---

Consider a hierarchical tree $T$ containing 9 nodes with root $A$:

• $A$ connects to children $B$ and $C$.
• $B$ connects to children $D$ and $E$.
• $C$ connects to child $F$.
• $E$ connects to children $G$ and $H$.
• $F$ connects to child $I$.

The table below catalogs every node's topological measurements and anatomical classification:

---

• Depth of Node $u$ ($\text{depth}(u)$): The number of edges on the unique path from root $r$ down to node $u$. By definition, $\text{depth}(\text{root})=0$.
• Height of Node $u$ ($\text{height}(u)$): The number of edges on the longest simple downward path from node $u$ to any leaf in its subtree. For all leaves, $\text{height}(\text{leaf})=0$.
• Height of Tree $T$ ($\text{height}(T)$): The height of the root node: $\text{height}(T)=\text{height}(r)={\max }_{u\in V}\text{depth}(u)$. For the tree above, $\text{height}(T)=3$.
• Degree of Node $u$ ($\text{deg}(u)$): In rooted trees, this refers to the out-degree (the number of children attached to $u$).
• Degree of Tree ($\text{degree}(T)$): The maximum degree across all nodes: $\text{degree}(T)={\max }_{u\in V}{\text{deg}}^{+}(u)$. For binary trees, $\text{degree}(T)\le 2$.
• Subtree: A tree consisting of a node $u$ and all of its descendants, retaining all connecting edges.

---

For any connected tree $T=(V,E)$ containing $|V|=N$ nodes:

Proof:

In any rooted tree, every node except the root has exactly one incoming edge connecting it to its parent. Because the root has zero incoming edges, the total number of edges equals the sum of in-degrees of all non-root nodes:

---

In any binary tree, level $i$ (where the root is defined as level $0$) contains at most:

Proof (By Mathematical Induction):

• Base Case ($i=0$): At level $0$, there is only the root node. $2^0=1$. The base case holds.
• Inductive Step: Assume level $k$ has at most $2^k$ nodes. Each node in a binary tree has at most $2$ children. Therefore, the number of nodes at level $k+1$ is at most:
  $$N_{\text{level}}(k+1)\le 2\times N_{\text{level}}(k)\le 2\times 2^k=2^{k+1}$$
  By induction, level $i$ contains at most $2^i$ nodes for all $i\ge 0$. $■$

---

A binary tree of height $h$ can contain at most:

Conversely, for a binary tree with $N$ nodes, its height is lower-bounded by:

---

In any non-empty full (strict) binary tree where every node has either 0 or 2 children:

where $L$ is the number of leaf nodes and $I$ is the number of internal nodes.

Proof:

1. Total nodes $N=L+I$.
2. Every internal node contributes exactly 2 outgoing edges, while leaves contribute 0 outgoing edges:
   $$|E|=2I$$
3. By Theorem 1, $|E|=N-1$:
   $$2I=N-1=(L+I)-1$$
4. Subtracting $I$ from both sides:
   $$I=L-1⟹L=I+1■$$

---

A Binary Tree is a specialized tree in which every node has at most two children, designated as the Left Child and the Right Child. Binary trees are categorized into five distinct structural archetypes based on balance and level fullness.

---

Complete Binary Trees possess an exceptional architectural property: they can be stored contiguously in a flat array without allocating any pointer variables (left, right, parent). The tree hierarchy is maintained entirely through arithmetic index relationships.

For an $n$-element Complete Binary Tree mapped into zero-based array $A[0\dots n-1]$ via level-order indexing:

• Root Element: Stored at index $0$.
• Left Child of Node $i$:
  $$\text{left}(i)=2i+1(\text{valid if }2i+1<n)$$
• Right Child of Node $i$:
  $$\text{right}(i)=2i+2(\text{valid if }2i+2<n)$$
• Parent of Node $i$ ($i>0$):
  $$\text{parent}(i)=\lfloor \frac{i-1}{2}\rfloor$$

Array Mapping Trace: 6-Node Complete Tree ($A=[A,B,C,D,E,F]$)

Hardware & Cache Advantage:
Because the tree nodes reside in contiguous memory, traversing parent-child relationships incurs zero pointer-dereference latency. Sequential memory reads maximize L1 CPU cache line utilization and eliminate the 16-to-24 byte per-node pointer overhead required by traditional dynamic tree node allocations.

---

1. Topological Tree Invariant: A tree of $N$ nodes contains strictly $N-1$ edges and zero cycles. Every non-root node has an in-degree of exactly 1.
2. Depth vs Height: Node depth counts edges from the root down to the node; node height counts edges on the longest downward path from the node to a leaf. The tree height is the height of its root.
3. Full Binary Tree Relation: In any full binary tree (where each node has either 0 or 2 children), the number of leaves is always one greater than the number of internal nodes: $L=I+1$.
4. Complete Binary Tree Array Mapping: Complete binary trees map into flat arrays with zero pointer overhead using arithmetic indexing ($2i+1,2i+2,\lfloor (i-1)/2\rfloor$), forming the physical basis for binary heaps.
5. The Cost of Imbalance: A degenerate (skewed) binary tree has height $h=n-1$, collapsing tree operations from logarithmic $O(\log n)$ to linear $O(n)$ linked list scans. Maintaining balance is essential for performance.

---

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Appendix B.5: Trees & Chapter 12: Binary Search Trees. MIT Press.
2. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.), Section 2.3: Trees. Addison-Wesley.
3. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 3.2: Binary Search Trees. Addison-Wesley.