5.2 Binary Tree Representation and Traversals

Binary Tree Representation

Binary trees organize data in a hierarchy where each node has at most two children (left and right). This structure is the foundation for binary search trees, heaps, and expression trees, so understanding how to represent and traverse them is essential for nearly everything else in this unit.

Linked vs. Array Representation

Linked representation is the more common approach. Each node is an object (or struct) containing three things: the data, a reference to the left child, and a reference to the right child. If a child doesn't exist, that reference is null.

• Nodes are dynamically allocated, so the tree can grow or shrink as needed
• Inserting or deleting a node only requires updating a few references
• Each node carries extra memory overhead for storing two pointers

Array representation stores the entire tree in a single array using index math to find relatives:

• For a node at index $i$:
  • Left child is at $2i + 1$
  • Right child is at $2i + 2$
  • Parent is at $\lfloor (i - 1) / 2 \rfloor$
• The root always sits at index $0$

Array representation works well for complete or nearly complete binary trees (like heaps), where most positions are filled. For sparse trees with many missing nodes, you end up wasting array slots on empty positions.

Binary Tree Traversals

Traversal means visiting every node in the tree exactly once in a specific order. The three classic depth-first traversals differ only in when you process the current node relative to its children.

The Three Depth-First Traversals

Preorder (NLR: Node, Left, Right)

1. Process the current node
2. Recursively traverse the left subtree
3. Recursively traverse the right subtree

Preorder visits the root before anything else, so it's useful for copying a tree or generating a prefix expression from an expression tree.

Inorder (LNR: Left, Node, Right)

1. Recursively traverse the left subtree
2. Process the current node
3. Recursively traverse the right subtree

For a binary search tree, inorder traversal produces elements in sorted (non-decreasing) order. This is the traversal you'll reach for most often when working with BSTs.

Postorder (LRN: Left, Right, Node)

1. Recursively traverse the left subtree
2. Recursively traverse the right subtree
3. Process the current node

Postorder processes children before their parent, making it the right choice for deleting a tree (you free children before the parent) or evaluating a postfix expression.

Recursive vs. Iterative Implementation

Recursive algorithms are the natural fit for tree traversals because trees are recursive structures.

• Base case: if the node is null, return (do nothing)
• Recursive case: process the node and recurse on left/right children in the appropriate order
• Clean and easy to read, but each recursive call adds a frame to the call stack

Iterative algorithms replace the implicit call stack with an explicit stack (or queue) data structure. These are trickier to write but avoid stack overflow on very deep trees.

• Preorder (iterative): Push the root onto a stack. Pop a node, process it, then push its right child followed by its left child. (Right goes first so left gets popped first.)
• Inorder (iterative): Start at the root and push all left descendants onto the stack. Pop a node, process it, then move to its right child and repeat.
• Postorder (iterative): The trickiest of the three. One common approach uses two stacks: run a modified preorder (node, right, left) pushing results onto a second stack, then pop the second stack to get postorder.

Applications of Tree Traversals

Evaluating expression trees Arithmetic expressions like $(3 + 5) \times 2$ can be stored as binary trees where operators are internal nodes and operands are leaves. A postorder traversal evaluates the expression bottom-up: compute each subtree's value before applying the parent operator.

Serialization and deserialization To save a tree to a file or send it over a network, you convert it to a linear format (a string or array) using preorder or postorder traversal, with a special marker (like # or null) for missing children. To reconstruct the tree, you read the sequence back in the same traversal order.

Computing tree properties

• Height: Use postorder traversal. The height of a node is $\max(\text{height of left subtree}, \text{height of right subtree}) + 1$. A null node has height $-1$ (or $0$, depending on your convention).
• Balance check: A tree is balanced if, for every node, the left and right subtree heights differ by at most 1. You can check this during a postorder height computation.
• BST validation: An inorder traversal of a valid BST produces a strictly sorted sequence. If any element is out of order, the tree isn't a valid BST.
• Lowest common ancestor (LCA): Recurse through the tree. If the current node matches either target, return it. Otherwise, search both subtrees. If both subtrees return non-null results, the current node is the LCA.