Rooted and Binary Trees

Tree Terminology

A rooted tree is a data structure with a single entry point (the root) and hierarchical parent-child relationships. Every node except the root has exactly one parent; the root has none.

Term	Definition
Root	The unique topmost node with no parent
Parent	The node directly above a given node
Child	A node directly below a given node
Sibling	Nodes sharing the same parent
Leaf (external node)	A node with no children
Internal node	A node with at least one child
Depth of a node	Number of edges from root to that node (root has depth 0)
Height of a node	Number of edges on the longest path from that node to a leaf
Height of the tree	Height of the root
Level	Set of nodes at the same depth
Ancestor / descendant	Nodes on the path toward/away from the root

Binary Trees

A binary tree is a rooted tree where each node has at most two children, designated as left child and right child. A child can be NIL (absent).

Types of binary trees:

• Full binary tree: every node has 0 or 2 children.
• Complete binary tree: all levels are completely filled except possibly the last, which is filled from left to right.
• Perfect binary tree: all leaves are at the same depth; every internal node has exactly 2 children. A perfect binary tree of height $h$ has $2^{h+1} - 1$ nodes.

Height Bounds

For a binary tree with $n$ nodes:

• Minimum height: $\lfloor \log_2 n \rfloor$, achieved by a complete/perfect binary tree.
• Maximum height: $n - 1$, when every internal node has exactly one child (a degenerate tree, essentially a linked list).

Thus a balanced binary tree is one whose height is $O(\log n)$, giving logarithmic-time operations. An unbalanced tree degenerates to $O(n)$ height.

Tree Traversals

Three fundamental depth-first traversals of a binary tree:

Traversal	Order	Visits root
Preorder	Root, then left subtree, then right subtree	First
Inorder	Left subtree, then root, then right subtree	Middle
Postorder	Left subtree, then right subtree, then root	Last

Example tree with root $R$, left child $A$, right child $B$ (where $A$ has left child $C$, right child $D$):

• Preorder: $[R, A, C, D, B]$
• Inorder: $[C, A, D, R, B]$
• Postorder: $[C, D, A, B, R]$

Inorder traversal of a binary search tree visits keys in sorted order.

Array Representation of Binary Trees

Store a complete binary tree in an array A[1..n]:

Node	Array index
Root	A[1]
Parent of $i$	A[floor(i/2)]
Left child of $i$	A[2i]
Right child of $i$	A[2i + 1]

This is the representation used for heaps. No explicit pointers are needed; the tree structure is encoded in the indices. The condition for a child to exist is $2i \le \text{heap\_size}$ (or $2i + 1 \le \text{heap\_size}$).

Pointer-Based Representation

Each node is an object with fields:

class TreeNode:
    key       # data
    left      # pointer to left child (or NIL)
    right     # pointer to right child (or NIL)
    parent    # pointer to parent (or NIL), optional

Parent pointers are required for algorithms like PREDECESSOR and SUCCESSOR in BSTs, and for efficient traversal without an explicit stack.

Trees with Unbounded Branching

When nodes can have arbitrarily many children, a linked list of children is used rather than fixed left/right pointers. An alternative is the left-child, right-sibling representation: each node has a pointer to its first child and a pointer to its next sibling. This encodes any tree as a binary tree.

Binary Search Trees (Preview)

A BST is a binary tree satisfying the BST property: for every node $x$, all keys in the left subtree are strictly less than $x.\!key$, and all keys in the right subtree are strictly greater. BSTs support SEARCH, INSERT, DELETE, MINIMUM, MAXIMUM, PREDECESSOR, and SUCCESSOR in $O(h)$ time where $h$ is the tree height. With balanced trees, $h = O(\log n)$; with degenerate trees, $h = O(n)$.

Summary

Property	Value
Min height (balanced)	$\lfloor \log_2 n \rfloor$
Max height (degenerate)	$n - 1$
Perfect tree size	$2^{h+1} - 1$ nodes
Array rep.: left child	$2i$
Array rep.: right child	$2i + 1$
Preorder	Root → left → right
Inorder	Left → root → right (sorted for BSTs)
Postorder	Left → right → root
BST property	Left subtree $<$ root $<$ right subtree