L1. Introduction to Trees | Types of Trees

Trees are fundamental non-linear, hierarchical data structures used extensively in computer science to model parent-child relationships, directory structures, and optimize search operations. Unlike linear data structures such as arrays, stacks, queues, and linked lists, trees organize data in multiple dimensions, making them essential for high-performance computing and technical interviews.

1. Why Do We Need Trees? (The Status Quo)

Linear data structures like arrays, stacks, queues, and linked lists store elements sequentially in a single line. While efficient for linear traversals, they fail when attempting to represent multi-layered relationships or organizational hierarchies.

Consider how your computer's operating system organizes files:

Structure & Concept Flow

Root Directory (C:\)

+-- Documents

| |-- Resume.pdf

| +-- Taxes.xlsx

+-- Programs

+-- Chrome

+-- chrome.exe

This multi-tiered parent-child relationship cannot be efficiently modeled using a simple array or linked list. Trees provide the exact hierarchical abstraction needed for file systems, XML/JSON parsing, routing algorithms, and database indexing.

2. Core Mental Model and Real-World Analogy

Real-Life Analogy: Corporate Organizational Chart or Family Genealogy

Think of a tree data structure like a company's corporate structure or a family tree. At the very top is the CEO or founder (the Root). Underneath them are department heads, who in turn manage team leads, down to individual contributors who have no reports beneath them (the Leaves).

Every person in the company reports to exactly one direct manager (their Parent), and anyone below them in their reporting chain is part of their Subtree.

3. Fundamental Tree Terminology

To work effectively with trees, several core structural terms must be mastered:

Root: The topmost node of the tree. It has no parents and serves as the entry point for all operations.
Node: An individual container in a tree that holds data and references (pointers) to its children.
Children: Nodes that descend directly from a parent node. In a Binary Tree, each node can have at maximum 2 children (referred to conventionally as the left child and right child).
Leaf Node: A node that has zero children. It sits at the absolute periphery of the tree.
Subtree: Any node in the tree, combined with all of its descendants (children, grandchildren, etc.), forms a valid subtree of that node.
Ancestors: For any given node, its ancestors include its parent, grandparent, great-grandparent, and so on, tracing all the way back up to the root.

4. Introduction to Binary Trees

A Binary Tree is a specific type of hierarchical data structure where every node has at maximum two children (0, 1, or 2 children).

CODE

       [Root: 10]
        /      \
      [5]      [20]
      /        /  \
    [2]      [15]  [25]

Why Binary Trees?

Binary trees form the structural foundation for advanced data structures like Binary Search Trees (BSTs), Heaps, and AVL Trees. Their restricted branching factor simplifies recursive algorithms and search patterns in interviews and real-world systems.

5. Types of Binary Trees

The lecture highlights five primary classifications of binary trees, each with strict structural rules:

Type of Binary Tree	Defining Structural Rule	Visual Characteristic / Example
1. Full Binary Tree	Every node has either 0 or 2 children. No node can have exactly 1 child.	Every parent is either a leaf or has a pair of children.
2. Complete Binary Tree	All levels are completely filled except possibly the last level, and all nodes in the last level are as far left as possible.	Perfectly packed from top-left to bottom-left.
3. Perfect Binary Tree	All internal nodes have 2 children, and all leaf nodes are at the exact same level (depth).	Symmetric triangle shape where every row is completely full.
4. Balanced Binary Tree	The height of the tree is constrained to a maximum of $\log_2(n)$ (where $n$ is the number of nodes).	Prevents skewed growth to guarantee efficient $O(\log n)$ search times.
5. Degenerate Tree (Skewed Tree)	Every parent node has only 1 child. The tree collapses into a straight line.	Structurally identical to a linked list; worst-case time complexity $O(n)$ .

6. Deep Dive: Full vs. Complete vs. Perfect Binary Trees

Full Binary Tree Rule

A node can never have a single orphan child. It either branches into two children or terminates completely as a leaf.

CODE

Valid Full Binary Tree:      Invalid Full Binary Tree:
        [10]                           [10]
       /    \                         /    \
     [5]    [20]                    [5]    [20]
     / \                             /
   [1] [2]                         [1]  (Has only 1 child!)

Complete Binary Tree Rule

Levels must fill sequentially from top to bottom. On the final level, nodes must pack tightly to the left side:

CODE

Valid Complete Tree:         Invalid Complete Tree (Node on right, gap on left):
      [1]                              [1]
     /   \                            /   \
   [2]   [3]                        [2]   [3]
   /                                         \
 [4]                                         [4] (Not left-aligned!)

Perfect Binary Tree Rule

Every single leaf sits neatly on the bottom-most floor, and every non-leaf node branches twice.

Structure & Concept Flow

[1] <- Level 0 (1 node)

/ \

[2] [3] <- Level 1 (2 nodes)

/ \ / \

[4][5] [6][7] <- Level 2 (4 nodes, all leaves)

7. Performance Implications: Balanced vs. Degenerate Trees

Balanced Binary Trees

By ensuring the height $h$ remains logarithmic relative to the node count ( $h \le \log_2 n$ ), operations like search, insertion, and deletion execute efficiently in $O(\log n)$ time.

Degenerate (Skewed) Trees

When insertions occur in sorted order without rebalancing, a binary tree can degenerate into a linear chain:

CODE

Note: A degenerate binary tree functions identically to a Singly Linked List, destroying logarithmic search advantages and degrading time complexity to $O(n)$ . This limitation motivates the creation of Self-Balancing Binary Search Trees (such as AVL and Red-Black Trees).

Summary and Key Takeaways

Hierarchical Nature: Trees organize data multi-dimensionally, unlike linear data structures (arrays, stacks, queues, linked lists).
Binary Tree Constraint: A binary tree restricts every node to having a maximum of two children (left and right).
The Root: The foundational starting node of any tree from which all traversals and subtrees originate.
Leaf Nodes: Terminal nodes possessing zero children that sit at the boundaries of the hierarchy.
Subtrees: Any node combined with all of its descendants forms a self-contained subtree.
Full Binary Tree: Every node has strictly 0 or 2 children (no single-child nodes allowed).
Complete Binary Tree: All levels are completely filled except the last, which must be packed as far left as possible.
Perfect Binary Tree: All internal nodes have 2 children, and all leaf nodes reside on the exact same level.
Balanced Binary Trees: Constrain maximum height to $\log_2(n)$ to optimize search and traversal performance.
Degenerate Trees: Skewed trees where every node has only 1 child, rendering the tree functionally equivalent to a linked list with $O(n)$ worst-case performance.