Computer Science (9645) | Tree algorithms

Welcome to Advanced Algorithms: Tree Algorithms!

Hi everyone! This chapter dives into one of the most powerful and fundamental non-linear data structures in computer science: the Tree. You might think of trees as simple diagrams, but algorithmically, they are crucial for organising data efficiently.

In this section, we will focus on understanding the structure of specific types of trees (especially the Binary Tree) and mastering the essential skill of tree traversal—the methods we use to visit every item in the tree. These algorithms are cornerstones of many complex data handling systems, from databases to compilers.

Don't worry if this seems tricky at first! We'll use clear steps and mnemonics to make tracing these algorithms straightforward. Let's get started!

1. Quick Review: What Exactly Is a Tree? (3.10.2)

Before we run algorithms on trees, let's quickly solidify the definitions from the Data Structures section.

A. Defining a Tree

In Computer Science, a tree is a special type of graph (a data structure used to represent complex relationships) characterized by two main properties:

• It is connected: You can get from any node to any other node.
• It has no cycles: You cannot start at a node and return to that same node without backtracking.

B. Rooted Trees and Binary Trees

While any structure meeting the above criteria is a tree, we often deal with rooted trees, which introduce hierarchy (parent-child relationships).

• Rooted Tree: A tree where one node is specifically designated as the root.
  • The root is the only node with no parent.
  • All other nodes are descendants of the root.
  • Nodes below a given node are its children.
• Binary Tree: A rooted tree where every node has at most two children. These children are usually referred to as the left child and the right child.

---

Key Takeaway: Trees are hierarchical, cycle-free structures. We primarily focus on Binary Trees.

---

2. The Binary Search Tree (BST)

One of the most common and useful applications of a binary tree is the Binary Search Tree (BST). This specific structure allows for extremely efficient searching, insertion, and deletion.

Properties of a Binary Search Tree (BST)

For every node in a BST:

• All data values in its Left Subtree are less than the data value of the node itself.
• All data values in its Right Subtree are greater than the data value of the node itself.

Did you know? Because of these strict ordering rules, BSTs are the perfect candidates for one of the traversal algorithms below.

3. Tree Traversal Algorithms (3.11.2)

Tree Traversal is the process of visiting every node in a tree exactly once, following a specific order. Unlike lists or arrays, which have a natural linear order, trees can be processed in several different sequences.

The three main recursive traversal algorithms are defined based on when the central Node (Root) is processed relative to its Left (L) and Right (R) subtrees.

A. Pre-order Traversal (NLR: Node, Left, Right)

In Pre-order traversal, you visit the Node (Root) first, then recursively visit the Left Subtree, and finally recursively visit the Right Subtree.

Step-by-Step Trace (The "Root First" Rule)

1. Visit the Node (N) (process the data).
2. Traverse the Left Subtree (L) recursively.
3. Traverse the Right Subtree (R) recursively.

Memory Aid: Pre-order means the root node is Prioritised and visited Pre-emptively.

Applications of Pre-order Traversal (3.11.2)

• Copying a Tree: If you want to create an exact structural duplicate of a tree, processing the root first ensures the structure is accurately rebuilt.
• Producing a Prefix Expression (Polish Notation): Pre-order traversal of an Expression Tree generates the arithmetic expression where the operator comes before the operands (e.g., \(+ \ A \ B\)).

B. In-order Traversal (LNR: Left, Node, Right)

In In-order traversal, you visit the Left Subtree first, then visit the Node (Root), and finally the Right Subtree.

Step-by-Step Trace (The "Node in the Middle" Rule)

1. Traverse the Left Subtree (L) recursively.
2. Visit the Node (N) (process the data).
3. Traverse the Right Subtree (R) recursively.

Memory Aid: In-order puts the root IN the middle of the left and right visits.

Application of In-order Traversal (3.11.2)

This is the most famous application, especially for BSTs:

• Outputting contents of a Binary Search Tree (BST) in Ascending Order: Since a BST is defined by the rule Left < Node < Right, visiting the nodes in the LNR order naturally prints the data in sorted (ascending) sequence.

C. Post-order Traversal (LRN: Left, Right, Node)

In Post-order traversal, you visit both the Left and Right Subtrees recursively before you visit the Node (Root) itself.

Step-by-Step Trace (The "Root Last" Rule)

1. Traverse the Left Subtree (L) recursively.
2. Traverse the Right Subtree (R) recursively.
3. Visit the Node (N) (process the data).

Memory Aid: Post-order means the root node is POSTponed until the very end.

Applications of Post-order Traversal (3.11.2)

• Emptying a Tree (Deletion): To safely delete a tree, you must delete the children before deleting the parent. Post-order guarantees you process the leaf nodes first, working your way up to the root.
• Producing a Postfix Expression (Reverse Polish Notation): Post-order traversal of an Expression Tree generates the arithmetic expression where the operator comes after the operands (e.g., \(A \ B \ +\)).

---

4. Tracing Tree Traversal

Tracing is the practical skill you need to master. Remember that these are recursive algorithms: you always apply the rule (NLR, LNR, or LRN) to the current node and all its subtrees.

Let's imagine a simple binary tree where the nodes contain letters:
Root A (Parent to B and C)
B (Parent to D and E)
C (Leaf node)
D (Leaf node)
E (Leaf node)
Structure: A is the root. Left child is B, Right child is C. B's children are D (Left) and E (Right).

A. Tracing Pre-order (NLR)

Start at A (Root).

1. N: Visit A. (Output: A)
2. L: Go Left to B. Apply NLR to B.
   1. N: Visit B. (Output: A, B)
   2. L: Go Left to D. Apply NLR to D.
      1. N: Visit D. (Output: A, B, D)
      2. L/R: D has no children. Return.
   3. R: Go Right to E. Apply NLR to E.
      1. N: Visit E. (Output: A, B, D, E)
      2. L/R: E has no children. Return.
3. R: Go Right from A to C. Apply NLR to C.
   1. N: Visit C. (Output: A, B, D, E, C)
   2. L/R: C has no children. Return.

Final Pre-order Sequence: A, B, D, E, C

B. Tracing In-order (LNR)

Start at A (Root).

1. L: Go Left to B. Apply LNR to B.
   1. L: Go Left to D. Apply LNR to D.
      1. L: D has no left child.
      2. N: Visit D. (Output: D)
      3. R: D has no right child. Return to B.
   2. N: Visit B. (Output: D, B)
   3. R: Go Right to E. Apply LNR to E.
      1. L: E has no left child.
      2. N: Visit E. (Output: D, B, E)
      3. R: E has no right child. Return to A.
2. N: Visit A. (Output: D, B, E, A)
3. R: Go Right to C. Apply LNR to C.
   1. L: C has no left child.
   2. N: Visit C. (Output: D, B, E, A, C)
   3. R: C has no right child. Return.

Final In-order Sequence: D, B, E, A, C

Notice how if these were numbers in a BST, this sequence would be sorted!

C. Tracing Post-order (LRN)

Start at A (Root).

1. L: Go Left to B. Apply LRN to B.
   1. L: Go Left to D. Apply LRN to D.
      1. L/R: D has no children.
      2. N: Visit D. (Output: D)
      3. Return to B.
   2. R: Go Right to E. Apply LRN to E.
      1. L/R: E has no children.
      2. N: Visit E. (Output: D, E)
      3. Return to B.
   3. N: Visit B. (Output: D, E, B)
   4. Return to A.
2. R: Go Right to C. Apply LRN to C.
   1. L/R: C has no children.
   2. N: Visit C. (Output: D, E, B, C)
   3. Return to A.
3. N: Visit A. (Output: D, E, B, C, A)

Final Post-order Sequence: D, E, B, C, A

---

Key Takeaway: Tracing recursive traversal involves applying the three-step rule (L, N, R) to the current node, immediately jumping to the left or right if that step is another subtree traversal.

---

5. Implementing Tree Traversal (Conceptual)

Although you might not be asked to write the code for these complex algorithms in the exam, understanding the conceptual implementation (often done recursively) is vital.

Recursive Structure

All three traversals typically follow a similar recursive blueprint, which relies on the subroutine calling itself on the left and right children.

Example Pseudocode structure for Pre-order:

        
    SUBROUTINE PreOrder(Node)
        IF Node IS NOT NULL THEN
            // 1. Visit Node (N)
            OUTPUT Node.Data
            // 2. Traverse Left (L)
            PreOrder(Node.LeftChild)
            // 3. Traverse Right (R)
            PreOrder(Node.RightChild)
        END IF
    END SUBROUTINE
        
    

To change this to In-order, you would simply move the OUTPUT Node.Data line to between the calls to the left and right subroutines.

To change this to Post-order, you would move the OUTPUT Node.Data line to after both recursive calls.

---

Key Takeaway: Implementation relies on recursion, where the position of the "Visit Node" step determines the traversal type.

---