All subjects · Computer Science · WCP04 Advanced Practical Programming and Problem-solving

Recursive tree traversals: pre-order, in-order and post-order

Edexcel IAL Computer Science · WCP04 Advanced Practical Programming and Problem-solving

Traversing a tree means visiting every node exactly once. The three depth-first traversals differ only in when the current node is visited compared with its two subtrees, and each is a short recursive procedure.

Practise this in the app: instant marking and a fix for every mistake. Free, no email needed to start.

Practise this lesson

Three orders

Pre-order: visit the node, then traverse left, then right. Gives a copy order: inserting the output into an empty BST rebuilds the same tree.
In-order: left, node, right. For a BST this outputs the values in ascending order.
Post-order: left, right, node. Children are dealt with before their parent, so it suits deleting a tree or evaluating an expression tree.

The base case is an empty subtree (None), where the procedure does nothing.

The code

All three procedures have the same shape; only the position of the print line moves. The Node class and the insert, find and build code from the BST lesson are repeated first so the program runs on its own.

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

def insert(node, value):
    if value < node.data:
        if node.left is None:
            node.left = Node(value)
        else:
            insert(node.left, value)
    elif value > node.data:
        if node.right is None:
            node.right = Node(value)
        else:
            insert(node.right, value)
    # equal values are ignored: no duplicates

def find(node, target):
    while node is not None:
        if target == node.data:
            return True
        node = node.left if target < node.data else node.right
    return False

def build(values):
    root = Node(values[0])
    for v in values[1:]:
        insert(root, v)
    return root

def pre_order(node):
    if node is not None:
        print(node.data, end=" ")
        pre_order(node.left)
        pre_order(node.right)

def in_order(node):
    if node is not None:
        in_order(node.left)
        print(node.data, end=" ")
        in_order(node.right)

def post_order(node):
    if node is not None:
        post_order(node.left)
        post_order(node.right)
        print(node.data, end=" ")

root = build([50, 30, 70, 20, 40, 60, 80])
pre_order(root); print()
in_order(root); print()
post_order(root); print()

Output:

50 30 20 40 70 60 80 
20 30 40 50 60 70 80 
20 40 30 60 80 70 50

Tracing a traversal by hand

A quick method: draw the tree, then trace a line round the outside starting left of the root.

Pre-order lists each node as you pass its left side.
In-order lists each node as you pass underneath it.
Post-order lists each node as you pass its right side.

The recursion uses the call stack: each call waits for its left subtree to finish before continuing.

Worked example

Write a recursive function that returns the in-order traversal as a list, rather than printing it, so the result can be tested.

```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(node, value): if value < node.data: if node.left is None: node.left = Node(value) else: insert(node.left, value) elif value > node.data: if node.right is None: node.right = Node(value) else: insert(node.right, value) # equal values are ignored: no duplicates def find(node, target): while node is not None: if target == node.data: return True node = node.left if target < node.data else node.right return False def build(values): root = Node(values[0]) for v in values[1:]: insert(root, v) return root def in_order_list(node): if node is None: return [] return in_order_list(node.left) + [node.data] + in_order_list(node.right) print(in_order_list(build(["kiwi", "fig", "pear", "apple", "lime"]))) ```
Output: ``` ['apple', 'fig', 'kiwi', 'lime', 'pear'] ```

Answer: The base case returns an empty list; each call joins its left result, its own data and its right result. The output is alphabetical.

Key idea: Pre-order: node, left, right. In-order: left, node, right (sorted for a BST). Post-order: left, right, node. Base case: an empty subtree does nothing.

Check yourself

Using the traversal procedures from the lesson, what does this print? ```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(node, value): if value < node.data: if node.left is None: node.left = Node(value) else: insert(node.left, value) elif value > node.data: if node.right is None: node.right = Node(value) else: insert(node.right, value) # equal values are ignored: no duplicates def find(node, target): while node is not None: if target == node.data: return True node = node.left if target < node.data else node.right return False def build(values): root = Node(values[0]) for v in values[1:]: insert(root, v) return root def pre_order(node): if node is not None: print(node.data, end=" ") pre_order(node.left) pre_order(node.right) def in_order(node): if node is not None: in_order(node.left) print(node.data, end=" ") in_order(node.right) def post_order(node): if node is not None: post_order(node.left) post_order(node.right) print(node.data, end=" ") pre_order(build([8, 3, 10, 1, 6, 14])) ```
Show answer
8 3 1 6 10 14. Visit 8, then its left subtree (3, 1, 6), then its right subtree (10, 14). Output: `8 3 1 6 10 14`
Using the traversal procedures from the lesson, what does this print? ```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(node, value): if value < node.data: if node.left is None: node.left = Node(value) else: insert(node.left, value) elif value > node.data: if node.right is None: node.right = Node(value) else: insert(node.right, value) # equal values are ignored: no duplicates def find(node, target): while node is not None: if target == node.data: return True node = node.left if target < node.data else node.right return False def build(values): root = Node(values[0]) for v in values[1:]: insert(root, v) return root def pre_order(node): if node is not None: print(node.data, end=" ") pre_order(node.left) pre_order(node.right) def in_order(node): if node is not None: in_order(node.left) print(node.data, end=" ") in_order(node.right) def post_order(node): if node is not None: post_order(node.left) post_order(node.right) print(node.data, end=" ") post_order(build([8, 3, 10, 1, 6, 14])) ```
Show answer
1 6 3 14 10 8. Left subtree first (1, 6, then 3), then right (14, then 10), then the root 8. Output: `1 6 3 14 10 8`
Using the traversal procedures from the lesson, what does this print? ```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(node, value): if value < node.data: if node.left is None: node.left = Node(value) else: insert(node.left, value) elif value > node.data: if node.right is None: node.right = Node(value) else: insert(node.right, value) # equal values are ignored: no duplicates def find(node, target): while node is not None: if target == node.data: return True node = node.left if target < node.data else node.right return False def build(values): root = Node(values[0]) for v in values[1:]: insert(root, v) return root def pre_order(node): if node is not None: print(node.data, end=" ") pre_order(node.left) pre_order(node.right) def in_order(node): if node is not None: in_order(node.left) print(node.data, end=" ") in_order(node.right) def post_order(node): if node is not None: post_order(node.left) post_order(node.right) print(node.data, end=" ") in_order(build(["dog", "cat", "emu", "ant"])) ```
Show answer
ant cat dog emu. In-order on a BST gives sorted order. Output: `ant cat dog emu`
Using the traversal procedures from the lesson, what does this print? ```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(node, value): if value < node.data: if node.left is None: node.left = Node(value) else: insert(node.left, value) elif value > node.data: if node.right is None: node.right = Node(value) else: insert(node.right, value) # equal values are ignored: no duplicates def find(node, target): while node is not None: if target == node.data: return True node = node.left if target < node.data else node.right return False def build(values): root = Node(values[0]) for v in values[1:]: insert(root, v) return root def pre_order(node): if node is not None: print(node.data, end=" ") pre_order(node.left) pre_order(node.right) def in_order(node): if node is not None: in_order(node.left) print(node.data, end=" ") in_order(node.right) def post_order(node): if node is not None: post_order(node.left) post_order(node.right) print(node.data, end=" ") pre_order(build([5, 2, 9, 7, 3])) ```
Show answer
5 2 3 9 7. Tree: 5 has left 2 (right child 3) and right 9 (left child 7). Pre-order: 5, 2, 3, 9, 7. Output: `5 2 3 9 7`
Which traversal of a binary search tree outputs its values in ascending order?
- Pre-order
- Post-order
- Level-order
- In-order
Show answer
In-order. Left subtree (smaller), node, right subtree (larger) at every level gives sorted output.
Which traversal is used to delete every node safely, because children are processed before their parent?
- Pre-order
- Post-order
- In-order
- Level-order
Show answer
Post-order. Post-order visits both subtrees before the node itself.
What is the base case in the recursive traversal procedures?
- The node is a leaf, so the procedure prints 'leaf'
- The node is the root
- The tree has more than 100 nodes
- The node is None, so the procedure returns without doing anything
Show answer
The node is None, so the procedure returns without doing anything. Every recursive call eventually reaches an empty child reference, which stops that branch.
Using the code from the lesson, what does this print? ```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(node, value): if value < node.data: if node.left is None: node.left = Node(value) else: insert(node.left, value) elif value > node.data: if node.right is None: node.right = Node(value) else: insert(node.right, value) # equal values are ignored: no duplicates def find(node, target): while node is not None: if target == node.data: return True node = node.left if target < node.data else node.right return False def build(values): root = Node(values[0]) for v in values[1:]: insert(root, v) return root def pre_order(node): if node is not None: print(node.data, end=" ") pre_order(node.left) pre_order(node.right) def in_order(node): if node is not None: in_order(node.left) print(node.data, end=" ") in_order(node.right) def post_order(node): if node is not None: post_order(node.left) post_order(node.right) print(node.data, end=" ") def count(node): if node is None: return 0 return 1 + count(node.left) + count(node.right) print(count(build([4, 2, 6, 1, 3, 5, 7, 2]))) ```
Show answer
7. Seven distinct values are inserted; the second 2 is a duplicate and is ignored, so the count is `7`.

Practise with instant feedback

Sources

Last updated 8 November 2026. Spotted a mistake? Tell us.