Algorithms for stacks, queues, trees, linked lists, depth-first (post-order) and breadth-first traversal

Algorithms for the main data structures, (stacks, queues, trees, linked lists, depth-first (post-order) and breadth-first traversal of trees).

2.3.1 Algorithms

Algorithms — Note 5 of 6

Candidates need to understand where stacks, queues, trees and linked lists can be used and justify their use in a scenario. Candidates need to be able to add and remove items (and search a linked list), and read, trace and write code to implement each structure, including using another structure such as a static array. Candidates need to be able to perform, and read, trace and write code for, depth-first (post-order) and breadth-first traversals of a tree.

What you need to know

You need to be able to read, trace and write code for the main data structures, and to perform depth-first (post-order) and breadth-first traversals of a tree. You also need to know where each structure is used.

What to know

Stack: push and pop at the top, checking for overflow and underflow. Uses: undo, call stack, backtracking, reversing data.
Queue: enqueue at the rear, dequeue from the front, checking for full and empty. Uses: print queues, task scheduling, breadth-first search.
Linked list: add, remove and search for items by following and updating pointers.
Tree: add and remove items; trees can be binary or multi-branch, and can be implemented using a linked list or arrays.
Post-order traversal is used, for example, to delete a tree (children before parents) or to evaluate an expression tree.

Key terms

Depth-first (post-order) traversal: Visit the left subtree, then the right subtree, then the node itself. Implemented recursively or with a stack.
Breadth-first traversal: Visit the root, then every node on the next level, left to right, level by level. Implemented with a queue.

Exam technique

Tip:When performing a traversal by hand, write the order in which nodes are output, step by step.
Mistake:Confusing post-order (left, right, node) with pre-order (node, left, right) or in-order (left, node, right).

Code examples

Depth-first (post-order) and breadth-first traversal

python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def post_order(node):
    if node is not None:
        post_order(node.left)     # left subtree
        post_order(node.right)    # right subtree
        print(node.data)          # then the node itself

def breadth_first(root):
    queue = [root]
    while len(queue) > 0:
        node = queue.pop(0)       # dequeue from the front
        print(node.data)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)

Traversal orders for an example tree

text

        D
      /   \
     B     F
    / \   / \
   A   C E   G

Post-order (left, right, node):  A C B E G F D
Breadth-first (level by level):   D B F A C E G