6.2 Traversals | Code Scholars Tutoring

How it works

In-order visits left, node, right and yields sorted order on a binary search tree. Pre-order suits copying, post-order suits deletion, and level-order needs a queue.

Choose the traversal by what the task requires rather than by habit.

Common error

Deleting a tree pre-order, which frees a parent while its children are still reachable only through it.

Worked example

Example

Tree: root 8; left 4; right 12
Preorder: node, left, right
Inorder: left, node, right
Postorder: left, right, node

The same tree produces different visit orders depending on when the node is processed. Inorder traversal of a binary search tree yields sorted keys when the tree obeys the chosen ordering and duplicate policy.

Root 8 has left child 4 and right child 12. — Visit order depends on whether the node is processed before, between, or after its subtrees.

Exercises

6.2.1 · Explain

Give preorder, inorder, and postorder for root 8 with left child 4 and right child 12.

Show solution

Preorder: 8, 4, 12. Inorder: 4, 8, 12. Postorder: 4, 12, 8.

6.2.2 · Write code

Implement inorder traversal for a tree rooted at 8 with children 4 and 12. Print its keys.

Show solution

Recursively process the left subtree, then the current node, then the right subtree.

One valid solution

class Node {
    int key; Node left, right;
    Node(int key) { this.key = key; }
}
class Walker {
    void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.key + " ");
        inorder(node.right);
    }
}
Node root = new Node(8);
root.left = new Node(4); root.right = new Node(12);
new Walker().inorder(root);

Expected output

4 8 12

Open Java compiler