Trees, Binary Trees, Traversals and Heaps

A tree represents hierarchical relationships. It consists of nodes connected by edges, with one distinguished node called the root. Every node other than the root has exactly one parent and a node may have zero or more children. Unlike a general graph, a tree is connected and has no cycle. Consequently, there is exactly one simple path between any two nodes and a nonempty tree with n nodes has n - 1 edges.

Trees appear in file systems, organization charts, syntax structures, search indexes, user interfaces and decision processes. Their recursive shape is fundamental: removing the root separates a tree into smaller trees called subtrees.

Tree Terminology

Nodes with the same parent are siblings. A node with no children is a leaf or external node; a node with at least one child is an internal node. An ancestor of a node lies on the path from the root to that node, while a descendant lies below it. A subtree rooted at node x contains x and all descendants of x.

The degree of a node is its number of children. The degree of a tree is the greatest node degree. A path’s length is its number of edges. Using edge counting, the root has depth zero and a node’s depth is the length of the root-to-node path. A node’s height is the length of the longest downward path from it to a leaf, so a leaf has height zero. The tree’s height is the root’s height. Some texts count nodes instead of edges; formulas are reliable only when the convention is stated.

An ordered tree distinguishes the positions of children. Swapping two children can therefore create a different tree. A forest is a collection of disjoint trees. Removing a tree’s root leaves a forest formed by the root’s child subtrees.

Binary Trees

A binary tree permits at most two children per node, identified as left and right. It is not simply a tree of degree two: child position matters, so a node with only a left child differs from a node with only a right child.

Several related shapes must be distinguished:

• A full or proper binary tree gives every node either zero or two children.
• A perfect binary tree has two children at every internal node and all leaves at the same depth.
• A complete binary tree fills every level except possibly the final level and fills the final level from left to right.
• A balanced tree keeps subtree heights within some defined bound so that overall height remains logarithmic.
• A skewed tree has nodes mainly along one side and can have height n - 1.

A perfect binary tree of height h has 2^(h + 1) - 1 nodes and 2^h leaves. A binary tree with n nodes has minimum possible height approximately log2(n) when compact and maximum height n - 1 when completely skewed.

Linked and Array Representations

A linked binary node contains data and references to its left and right children. A null reference represents an absent child. This form supports arbitrary shapes without reserving space for missing positions. Parent references can be added when algorithms need efficient upward movement, at the cost of another invariant.

A complete or almost complete binary tree maps efficiently into an array. With zero-based indexing, node i has left child 2i + 1, right child 2i + 2 and, for i > 0, parent (i - 1) / 2 using integer division. With one-based indexing, the corresponding formulas are 2i, 2i + 1 and i / 2. Mixing the two conventions produces incorrect navigation.

Array representation avoids link fields and has excellent locality for complete trees. It wastes space for sparse shapes because a node’s position determines the indices reserved for descendants even when many intermediate children are absent. Linked representation is usually better for irregular trees.

Depth-First Traversals

A traversal visits every node according to a defined order. The three standard recursive binary-tree traversals differ only in when the root is processed relative to its subtrees.

Preorder uses root, left, right. It processes the current node before its descendants. It is useful for copying tree structure, producing prefix expressions and serializing a tree when null markers or complementary traversal information preserve its shape.

Inorder uses left, root, right. On a binary search tree, it visits keys in nondecreasing order. Inorder is defined by binary child positions; a general tree with many children has no single corresponding inorder convention.

Postorder uses left, right, root. It processes children before their parent, which suits deleting an entire tree, calculating a directory’s aggregate size, evaluating expression trees and other bottom-up computations.

For a tree whose root is A, left subtree is rooted at B and right subtree is rooted at C, preorder begins with A, inorder visits the entire B subtree before A and postorder ends with A. Traversal order concerns the position of processing, not merely the order in which recursive calls are written.

Each complete traversal takes O(n) time because it visits every node once. Its recursive auxiliary space is O(h), where h is tree height. A balanced tree has O(log n) depth, while a skewed tree can require O(n) frames. Iterative traversals replace call frames with an explicit stack. Iterative preorder pushes the right child before the left so the left is popped first.

Breadth-First or Level-Order Traversal

Level-order traversal visits nodes by increasing depth, from left to right within a level. It uses a queue. Enqueue the root, then repeatedly dequeue a node, process it and enqueue its existing children. Children discovered earlier remain ahead of children discovered later, which preserves level order.

The traversal takes O(n) time. Its auxiliary space is proportional to the tree’s maximum width and can be O(n). Recording the queue size at the start of each level allows levels to be processed separately. Level-order traversal is useful for displaying hierarchy by depth, finding minimum-depth properties and serializing complete-tree positions.

Reconstructing and Serializing Trees

Traversal sequences can sometimes determine a tree. If keys are distinct, preorder plus inorder identifies a unique binary tree: the first preorder key is the root and its position in inorder divides left and right subtrees. Postorder plus inorder works similarly using the last postorder key. Preorder and postorder alone generally do not identify an arbitrary binary tree uniquely.

A serialized tree must preserve both values and shape. Preorder values alone cannot distinguish some structures. Including a marker for every null child makes reconstruction unambiguous. Level-order serialization can also include null positions, with a stated rule for trimming unnecessary trailing markers.

Expression Trees

An expression tree stores operands at leaves and operators at internal nodes. Inorder traversal resembles infix form, though parentheses may be required to preserve grouping. Preorder produces prefix form and postorder produces postfix form. Postorder evaluation recursively computes both operands before applying their parent operator.

Expression trees show how hierarchy captures precedence structurally. Once the tree is built, evaluation no longer needs an operator-precedence table because parent-child relationships state the grouping.

Binary Heaps

A binary heap combines a shape property with an order property. Its shape is a complete binary tree, enabling compact array storage. In a max-heap, each parent key is greater than or equal to its children. In a min-heap, each parent is less than or equal to its children. These local comparisons ensure that the root holds the maximum or minimum respectively.

Heap order is weaker than sorted order. In a max-heap, either child may be larger than the other and no required relationship exists between separate subtrees. Searching for an arbitrary key may therefore examine every node. A heap is designed for efficient access to one extreme, not general ordered lookup.

Insertion and Sift-Up

Insert a new item at the next free array position to preserve completeness. Compare it with its parent. If heap order is violated, exchange them and continue upward. This sift-up process travels at most the heap height, so insertion takes O(log n) worst-case time. It stops early when the parent relationship is valid.

Root Removal and Sift-Down

To remove the root, save its value, move the final array item to the root and reduce the heap size. Compare the replacement with its children and exchange it with the child that has better priority whenever order is violated. Repeating downward restores the heap in O(log n) time. In a max-heap, choosing the larger child is necessary; exchanging with the smaller child can leave a violation with the larger one.

Reading the root without removing it is O(1). Updating an item’s priority uses sift-up or sift-down according to the direction of the change, provided the item’s array position can be located efficiently.

Building a Heap

A heap can be built by inserting n items one at a time in O(n log n) time. Bottom-up heap construction is faster. Starting at the last internal node and moving backward to the root, sift each node down. Leaves already satisfy heap order. Although a single sift may be logarithmic, most nodes lie near the bottom and move only a short distance, so the total is O(n).

Heap Applications and Heapsort

A heap implements a priority queue: insert is O(log n), root access is O(1) and root removal is O(log n). Scheduling, event simulation, shortest-path algorithms and top-k selection use this interface.

Heapsort first builds a max-heap. It then repeatedly exchanges the root with the final item in the current heap, shrinks the heap boundary and sifts the new root down. The removed maxima accumulate in ascending order at the array’s end. Heapsort takes O(n log n) time in best, average and worst cases and uses O(1) auxiliary array space in its in-place form. It is generally not stable.

Structural Correctness

Tree algorithms should handle an empty root, a single node, one-sided nodes and deep skewed shapes. A linked-tree invariant checker can detect cycles or shared children when a proper tree is required, verify parent pointers and count reachable nodes. A heap checker verifies completeness through array bounds and compares every parent with its children.

The height of a tree controls the cost of operations that follow one root-to-leaf path. Completeness keeps heaps shallow, while later search-tree balancing techniques keep ordered-search trees shallow. Traversals remain linear because every node must be visited, regardless of shape; the shape mainly changes auxiliary depth and path-based operation costs.