07 Trees and Binary Search Trees

Tree Fundamentals

A Tree organizes data hierarchically. Its nodes are connected by edges, and unlike a general graph, it contains no cycles. There is exactly one path from the root to any other node.

Important relationships and measurements include:

• The root is the top node.

• A parent is directly above a child, and a child is directly below its parent.

• Siblings share the same parent.

• A leaf has no children; an internal node has at least one child.

• An ancestor lies on the path from a node toward the root, while a descendant lies in that node’s subtree.

• A subtree consists of a node together with all of its descendants.

• A node’s degree is its number of children.

• A node’s depth is its number of edges from the root. The root has depth $0$.

• A node’s height is the number of edges on its longest downward path to a leaf. The tree height is the height of its root.

• A level contains nodes at the same depth.

A forest is a collection of separate trees. Removing a tree’s root can produce a forest consisting of the root’s subtrees.

Takeaway: Tree terminology describes relationships among nodes and the structural measurements that determine how far operations may need to travel.

Binary Tree Structure

A binary tree is either empty or consists of a root and two disjoint subtrees: a left subtree and a right subtree. Each node has at most two children. The arrangement of values does not automatically impose an ordering.

Common structural classifications are:

• A full binary tree gives every node either zero or two children.

• A complete binary tree fills every level except possibly the last, with the last level filled from left to right.

• A perfect binary tree has two children at every internal node and places all leaves at the same depth.

• A skewed binary tree has many nodes with only one child, so it resembles a linked list.

• A balanced binary tree keeps height relatively small according to a specified balance condition.

A node can store a key and references named left and right. Either reference may be empty when the corresponding child does not exist.

Takeaway: Binary-tree classifications describe shape; ordering requires an additional binary search tree rule.

Traversal Orders

A tree traversal specifies the order in which nodes are visited. The four standard traversals are depth-first preorder, inorder, and postorder, plus breadth-first level-order traversal.

Consider a tree with root A, children B and C, lower-level nodes D, E, and F, where D and E are children of B and F is the child of C.

• Preorder traversal follows root, left, right, producing A, B, D, E, C, F.

• Inorder traversal follows left, root, right, producing B, D, E, A, C, F for this example.

• Postorder traversal follows left, right, root, producing D, E, B, F, C, A.

• Level-order traversal visits one depth level at a time, usually from left to right, producing A, B, C, D, E, F.

Level-order traversal is commonly implemented with a queue. Recursive depth-first traversals use auxiliary stack space of $O(h)$, where $h$ is the tree height. Every traversal visits all $n$ nodes once, so its running time is $\Theta(n)$.

Takeaway: Choose the traversal whose visit order matches the task: parents first for preorder, sorted output in a BST for inorder, descendants first for postorder, and breadth-by-depth processing for level order.

Binary Search Tree Ordering and Search

A Binary search tree adds an ordering rule to a binary tree. Under the common convention, every key in a node’s left subtree is less than the node’s key, and every key in its right subtree is greater. Duplicate keys must follow a consistent policy, such as always placing them in the right subtree.

To search for a target, begin at the root and compare the target with the current key:

1. If the current node is empty, the target is absent.

2. If the target equals the current key, the search succeeds.

3. If the target is smaller, continue in the left subtree.

4. If the target is larger, continue in the right subtree.

For example, searching for 7 in a tree rooted at 8, with 3 as its left child and 6 as a descendant of 3, follows the path 8, 3, 6, 7.

Because each comparison selects one subtree, search takes $O(h)$ time, where $h$ is the height. A balanced tree has height approximately $\log n$, giving $\Theta(\log n)$ search time; a completely skewed tree can have height $n-1$, giving $\Theta(n)$ time.

Takeaway: The BST property turns comparisons into a guided root-to-leaf search, but its benefit depends on keeping the height small.

BST Insertion

Insertion places a new key at a leaf while preserving the BST ordering. Follow the same comparisons used for search until an empty child position is reached, then create the new node there.

For example, inserting 5 follows the path 8, 3, 6, 4. Since $5>4$, the new node becomes the right child of 4.

A recursive insertion procedure returns the unchanged subtree root after inserting below it. If the key is less than the current key, recurse left; if it is greater, recurse right; if it is equal, apply the chosen duplicate policy.

Insertion follows one root-to-leaf path, so its running time is $O(h)$. It is $\Theta(\log n)$ in a balanced tree and can become $\Theta(n)$ in a skewed tree.

Takeaway: BST insertion is guided by comparisons and is efficient only when the tree height remains controlled.

BST Deletion Cases

BST deletion must preserve the ordering rule. The operation depends on the number of children of the node being removed.

1. Leaf: A node with no children can be removed by setting its parent’s corresponding child reference to empty.

2. One child: Connect the node’s parent directly to the node’s only child. If the deleted node is the root, the child becomes the new root.

3. Two children: Replace the node’s key with a neighboring key that preserves ordering, then delete the replacement node. The replacement can be the inorder successor, the smallest key in the right subtree, or the inorder predecessor, the largest key in the left subtree.

For example, deleting 8 from a tree whose right subtree begins with 10 can copy 10 into the root and then remove the original 10. The original 10 has at most one child, so the remaining deletion is simpler.

Deletion takes $O(h)$ time: typically $\Theta(\log n)$ in a balanced BST and potentially $\Theta(n)$ in a badly unbalanced BST.

Takeaway: The two-child case is handled by replacing the key with an adjacent inorder key and reducing the problem to a simpler deletion case.

Minimum, Maximum, and Sorted Output

The minimum key in a BST is found by repeatedly following left-child references until no left child remains. The maximum key is found symmetrically by repeatedly following right-child references.

An inorder traversal visits keys in ascending order under the BST ordering rule. Thus, inorder traversal can produce sorted output without separately sorting the keys.

Finding either extreme follows a single root-to-leaf path and takes $O(h)$ time. Producing all sorted output by traversal takes $\Theta(n)$, because every node must be visited.

Takeaway: Extreme keys are located at the far left or far right, while inorder traversal exposes the entire BST in sorted order.

Height, Balance, and Rotations

A BST’s performance is determined by height rather than by node count alone. Inserting already sorted values can create a chain in which each node has only one child. Such a tree has height near $n$, so its search behavior is similar to that of a linked list.

A balanced tree applies structural rules that prevent one subtree from becoming much deeper than the other. Balance does not necessarily mean that every pair of subtrees has exactly the same size.

Important approaches include:

• AVL trees maintain a strict height-balance condition and use rotations after updates.

• Red-black trees use node colors and structural rules to keep height logarithmic.

• 2–3 trees are height-balanced search trees whose internal nodes have two or three children.

• Splay trees move recently accessed nodes closer to the root and provide useful amortized performance without strict height balance.

A rotation changes a local parent-child arrangement while preserving the inorder sequence of keys. Rotations can repair a left-heavy or right-heavy region without violating the BST property.

Takeaway: Balancing methods trade additional structural work for a height near $\log n$, protecting search, insertion, and deletion from linear-time degeneration.

Complexity and Core Connections

Let $n$ denote the number of nodes and $h$ the tree height.

The main operation costs can be summarized as follows:

• Search: $O(h)$ for a general BST, $\Theta(\log n)$ for a balanced BST, and $\Theta(n)$ for a completely skewed BST.

• Insert: $O(h)$ for a general BST, $\Theta(\log n)$ for a balanced BST, and $\Theta(n)$ for a completely skewed BST.

• Delete: $O(h)$ for a general BST, $\Theta(\log n)$ for a balanced BST, and $\Theta(n)$ for a completely skewed BST.

• Find minimum or maximum: $O(h)$ for a general BST, $\Theta(\log n)$ for a balanced BST, and $\Theta(n)$ for a completely skewed BST.

• Traversal: $\Theta(n)$ regardless of tree shape, because every node must be visited.

• Extra recursive space: $O(h)$; this becomes $O(\log n)$ for a balanced tree and $O(n)$ for a completely skewed tree.

The shape of the tree affects operations that follow one root-to-leaf path. It does not change the linear cost of a full traversal.

Final takeaway: Trees provide hierarchical structure, binary trees restrict each node to two child positions, and BST ordering supports guided operations. Maintaining logarithmic height is the key to obtaining logarithmic search, insertion, deletion, and extreme-key operations.