CS 331 Practice — Prolog Trees & Graphs

P

Prolog: Trees & Graph Structures

Exam Intel Practice -- BST, tree operations, DFS/BFS

How Prolog Represents Binary Trees

Prolog has no built-in tree type. Instead, we use a convention based on two term constructors:

nil -- represents an empty tree (a leaf position with nothing in it)
node(Value, Left, Right) -- a tree node containing a value and two subtrees

Naming conventions vary by exam! Session 1 used Node(value, left, right) with empty for null. Session 2 used the same but for a key-value map. In SWI-Prolog, functors are always lowercase, so write node(...) not Node(...). If the exam template uses empty instead of nil, just replace nil with empty everywhere in your code — the logic is identical.

This is the standard representation used in virtually every Prolog textbook and exam. Every binary tree is either nil or node(V, L, R) where L and R are themselves binary trees.

Visual Example

Consider this tree:

In Prolog, this is represented as a single nested term:

node(5,
    node(3,
        node(1, nil, nil),
        node(4, nil, nil)),
    node(7, nil, nil))

Notice how every leaf node (1, 4, 7) has nil for both its left and right children. The entire tree is one compound term -- there are no pointers, no heap allocation, just nested structure.

Think of Russian nesting dolls -- each doll (node) contains a label and exactly two smaller dolls inside it. The smallest dolls that cannot be opened are nil. When you pattern match node(V, L, R), you are "opening" a doll to see its label and the two dolls inside.

Pattern Matching on Trees

Just as [H|T] destructures a list into its head and tail, node(V, L, R) destructures a tree into its value, left subtree, and right subtree. This is the fundamental technique for every tree predicate you will write.

% A predicate that prints the root value
print_root(node(V, _, _)) :-
    write(V), nl.

% A predicate that checks if a tree is a leaf
is_leaf(node(_, nil, nil)).

% A predicate that extracts the left subtree
left_child(node(_, L, _), L).

Tree Representation Recipe

Empty tree = nil (this is the base case for every recursive tree predicate)
Non-empty tree = node(Value, LeftSubtree, RightSubtree)
A leaf = node(V, nil, nil) -- both children are empty
Pattern matching: use node(V, L, R) in the head of a clause to destructure
Every tree predicate has at least two clauses: one for nil, one for node

Try It — Copy & Test

% === Save as tree_basics.pl ===
% Tree examples
print_root(node(V, _, _)) :- write(V), nl.
count_leaves(nil, 0).
count_leaves(node(_, nil, nil), 1).
count_leaves(node(_, L, R), C) :-
    count_leaves(L, CL), count_leaves(R, CR), C is CL + CR.

% === Test in SWI-Prolog ===
% $ swipl tree_basics.pl

?- print_root(node(5, node(3, nil, nil), node(7, nil, nil))).
   5
   true.

?- count_leaves(node(5, node(3, nil, nil), node(7, nil, nil)), C).
   C = 2.

?- node(V, _, _) = node(5, node(3,nil,nil), node(7,nil,nil)).
   V = 5.

2

BST Insert

Inserting an element into a Binary Search Tree

Three-Clause Insert

BST insertion in Prolog follows the same logic as in any language: if the tree is empty, create a new leaf; if the value is less than the current node, recurse left; otherwise, recurse right. The key difference is that Prolog does not mutate -- instead, it builds a new tree with the element inserted.

% Clause 1: inserting into an empty tree creates a leaf
bst_insert(X, nil, node(X, nil, nil)).

% Clause 2: X < V, so insert into the left subtree
bst_insert(X, node(V, L, R), node(V, NewL, R)) :-
    X < V, !,
    bst_insert(X, L, NewL).

% Clause 3: X >= V, so insert into the right subtree
bst_insert(X, node(V, L, R), node(V, L, NewR)) :-
    bst_insert(X, R, NewR).

Look carefully at the output argument (third position). In Clause 2, the result is node(V, NewL, R) -- the right subtree R is unchanged, and only the left subtree is replaced with NewL. In Clause 3, the opposite: node(V, L, NewR). This is how Prolog "rebuilds" the tree along the insertion path.

The cut (!) after X < V in Clause 2 is a green cut -- it does not change the logical meaning of the program, but prevents Prolog from uselessly trying Clause 3 when we already know the element goes left. Without the cut, the program is still correct but may do redundant work on backtracking.

Trace: bst_insert(3, node(5, node(2, nil, nil), node(7, nil, nil)), Result)

Step 1: Try Clause 1 -- second arg is node(...), not nil. Fail.
Step 2: Try Clause 2 -- X=3, V=5. Check 3 < 5? Yes. Cut. Recurse: bst_insert(3, node(2, nil, nil), NewL).
Step 3:   Try Clause 1 -- second arg is node(...), not nil. Fail.
Step 4:   Try Clause 2 -- X=3, V=2. Check 3 < 2? No. Fail.
Step 5:   Try Clause 3 -- X=3, V=2. Recurse: bst_insert(3, nil, NewR).
Step 6:     Try Clause 1 -- second arg is nil. Match! NewR = node(3, nil, nil).
Step 7:   Back in Step 5: NewL = node(2, nil, node(3, nil, nil)).
Step 8: Back in Step 2: Result = node(5, node(2, nil, node(3, nil, nil)), node(7, nil, nil)).

bst_insert/3 always returns a tree that is exactly one node larger than the input tree.

Try It — Copy & Test

% === Save as bst_insert.pl ===
% Clause 1: inserting into an empty tree creates a leaf
bst_insert(X, nil, node(X, nil, nil)).

% Clause 2: X < V, so insert into the left subtree
bst_insert(X, node(V, L, R), node(V, NewL, R)) :-
    X < V, !,
    bst_insert(X, L, NewL).

% Clause 3: X >= V, so insert into the right subtree
bst_insert(X, node(V, L, R), node(V, L, NewR)) :-
    bst_insert(X, R, NewR).

% === Test in SWI-Prolog ===
% $ swipl bst_insert.pl

?- bst_insert(3, nil, T).
   T = node(3, nil, nil).

?- bst_insert(3, node(5, nil, nil), T).
   T = node(5, node(3, nil, nil), nil).

?- bst_insert(7, node(5, nil, nil), T).
   T = node(5, nil, node(7, nil, nil)).

?- bst_insert(5, node(5, nil, nil), T).
   T = node(5, nil, node(5, nil, nil)).

3

Build BST from List

Accumulator pattern for folding a list into a tree

Accumulator-Based Construction

To build a BST from a list, we process elements one by one, inserting each into an accumulator tree that starts as nil. This is the classic fold-left pattern in Prolog.

% Public interface: start with an empty tree as accumulator
bst_build(List, Tree) :- bst_build(List, nil, Tree).

% Base case: no more elements, the accumulator IS the result
bst_build([], Tree, Tree).

% Recursive case: insert head, continue with tail
bst_build([H|T], Acc, Tree) :-
    bst_insert(H, Acc, NewAcc),
    bst_build(T, NewAcc, Tree).

The three-argument helper bst_build/3 carries the accumulator. Each step inserts the head of the remaining list into the current tree, producing a new accumulator. When the list is empty, the accumulator unifies with the result.

Trace: bst_build([5, 3, 7, 1, 4], Tree)

Step 1: Acc = nil. Insert 5 into nil. Acc = node(5, nil, nil).
Step 2: Insert 3 into node(5, nil, nil). 3 < 5, go left. Acc = node(5, node(3, nil, nil), nil).
Step 3: Insert 7. 7 >= 5, go right. Acc = node(5, node(3, nil, nil), node(7, nil, nil)).
Step 4: Insert 1. 1 < 5, go left. 1 < 3, go left. Acc = node(5, node(3, node(1, nil, nil), nil), node(7, nil, nil)).
Step 5: Insert 4. 4 < 5, go left. 4 >= 3, go right. Acc = node(5, node(3, node(1, nil, nil), node(4, nil, nil)), node(7, nil, nil)).
Result: Tree = node(5, node(3, node(1, nil, nil), node(4, nil, nil)), node(7, nil, nil)).

Mnemonic

Think of it like dealing cards onto a table. Each card finds its spot in the growing arrangement. The first card becomes the root. Each subsequent card walks down from the root to find its correct position, just like searching for where to place a new card in a sorted layout.

Key Points

The first element of the list becomes the root of the BST
Insertion order determines tree shape -- [1,2,3,4,5] produces a right-skewed tree
This is tail-recursive (the recursive call is the last thing in the clause body)
The accumulator pattern is the same one used for list reversal, sum, etc.

Try It — Copy & Test

% === Save as bst_build.pl ===
bst_insert(X, nil, node(X, nil, nil)).
bst_insert(X, node(V, L, R), node(V, NewL, R)) :-
    X < V, !,
    bst_insert(X, L, NewL).
bst_insert(X, node(V, L, R), node(V, L, NewR)) :-
    bst_insert(X, R, NewR).

bst_build(List, Tree) :- bst_build(List, nil, Tree).
bst_build([], Tree, Tree).
bst_build([H|T], Acc, Tree) :-
    bst_insert(H, Acc, NewAcc),
    bst_build(T, NewAcc, Tree).

% === Test in SWI-Prolog ===
% $ swipl bst_build.pl

?- bst_build([5, 3, 7, 1, 4], T).
   T = node(5, node(3, node(1,nil,nil), node(4,nil,nil)), node(7,nil,nil)).

?- bst_build([1, 2, 3], T).
   T = node(1, nil, node(2, nil, node(3, nil, nil))).

?- bst_build([], T).
   T = nil.

4

BST Search

Finding an element in a Binary Search Tree

Three-Clause Search

Searching a BST is simpler than insertion because we do not need to produce an output tree. We just need to succeed or fail. Three clauses handle the three cases: found, go left, go right.

% Found it: the value at the root matches
bst_search(X, node(X, _, _)).

% X is smaller than root, search left subtree
bst_search(X, node(V, L, _)) :-
    X < V,
    bst_search(X, L).

% X is greater than or equal to root, search right subtree
bst_search(X, node(V, _, R)) :-
    X >= V,
    bst_search(X, R).

Note how Clause 1 uses node(X, _, _) -- the same variable X appears both as the search target and as the node's value. This is Prolog's unification doing the equality check for us. No explicit =:= or == needed.

Also note: there is no clause for nil. If the search reaches an empty subtree, the predicate simply fails -- which is exactly what we want when the element is not in the tree.

In Clause 3, we use X >= V, not X > V. This matters if your BST can contain duplicates. If you inserted duplicates to the right (as our bst_insert does, since the third clause handles X >= V), then searching must also go right for equal values. Make sure your search logic matches your insert logic.

Insert vs. Search Comparison

Search has 2 arguments (target, tree); Insert has 3 (target, tree, result tree)
Search has no nil base case -- failure on nil means "not found"
Insert must have a nil clause -- that is where the new node gets created
Both use the same left/right branching logic based on comparing X with V

Try It — Copy & Test

% === Save as bst_search.pl ===
bst_insert(X, nil, node(X, nil, nil)).
bst_insert(X, node(V, L, R), node(V, NewL, R)) :-
    X < V, !,
    bst_insert(X, L, NewL).
bst_insert(X, node(V, L, R), node(V, L, NewR)) :-
    bst_insert(X, R, NewR).

bst_build(List, Tree) :- bst_build(List, nil, Tree).
bst_build([], Tree, Tree).
bst_build([H|T], Acc, Tree) :-
    bst_insert(H, Acc, NewAcc),
    bst_build(T, NewAcc, Tree).

bst_search(X, node(X, _, _)).
bst_search(X, node(V, L, _)) :-
    X < V,
    bst_search(X, L).
bst_search(X, node(V, _, R)) :-
    X >= V,
    bst_search(X, R).

% === Test in SWI-Prolog ===
% $ swipl bst_search.pl

?- bst_build([5,3,7,1,4], T), bst_search(4, T).
   true.

?- bst_build([5,3,7,1,4], T), bst_search(6, T).
   false.

?- bst_search(5, node(5, nil, nil)).
   true.

5

BST as a Key-Value Map (Session 2 Exam Topic)

Store key-value pairs in a BST — put, build, lookup

The Map Representation

Instead of storing just a value, each node stores a key-value pair. The tree is ordered by key. This turns a BST into a dictionary/map.

% Empty map
empty

% Node with key K, value V, left subtree L, right subtree R
node(Key, Value, Left, Right)

% Example: map with {2:3, 3:5, 5:1}
node(3, 5,
    node(2, 3, empty, empty),
    node(5, 1, empty, empty))

Think of it like a phone book sorted by name (key). Each entry has a name and a phone number (value). To find someone, you binary-search by name. To add someone, you insert by name.

put/4 — Insert or Update a Key-Value Pair

Four clauses: insert into empty, update existing key, go left, go right.

% Base case: empty map, create new node
put(Key, Val, empty, node(Key, Val, empty, empty)).

% Key already exists: UPDATE the value (keep same children)
put(Key, Val, node(Key, _, L, R), node(Key, Val, L, R)) :- !.

% Key is smaller: go left
put(Key, Val, node(K, V, L, R), node(K, V, NewL, R)) :-
    Key < K, !, put(Key, Val, L, NewL).

% Key is larger: go right
put(Key, Val, node(K, V, L, R), node(K, V, L, NewR)) :-
    put(Key, Val, R, NewR).

The update clause is critical! If the key already exists, you replace the value but keep the subtrees. The cut (!) after the update clause prevents falling through to the left/right clauses. This is what made Session 2 tricky — many forgot to handle the “key already exists” case.

Mental Trace: put(2, 4, node(3, 5, node(2, 3, empty, empty), node(5, 1, empty, empty)), Result)

put(2, 4, node(3,5, node(2,3,empty,empty), node(5,1,empty,empty)), R)
→ 2 < 3, so go left: put(2, 4, node(2,3,empty,empty), NewL)
→ Key matches! Update clause fires: NewL = node(2, 4, empty, empty)
→ R = node(3, 5, node(2, 4, empty, empty), node(5, 1, empty, empty))
Value of key 2 changed from 3 to 4. Everything else untouched.

build/2 — Build Map from a List of Pairs

The exam used Key-Value pairs (Prolog's built-in pair notation). Build = consecutive puts.

% Accumulator version (left fold)
build(Pairs, Map) :- build(Pairs, empty, Map).

build([], Map, Map).
build([Key-Val | Rest], Acc, Map) :-
    put(Key, Val, Acc, NewAcc),
    build(Rest, NewAcc, Map).

% Usage:
% ?- build([2-3, 3-5, 5-1], Map).
% Map = node(2, 3, empty, node(3, 5, empty, node(5, 1, empty, empty)))

Memory Anchor: The Dash Notation

In Prolog, 2-3 is syntactic sugar for the term -(2, 3). You pattern-match it as Key-Val. This is NOT subtraction — it’s a pair. You’ll also see it in msort/2 and pairs_keys_values/3.

lookup/3 — Find a Value by Key

lookup(Key, node(Key, Val, _, _), Val) :- !.
lookup(Key, node(K, _, L, _), Val) :-
    Key < K, !, lookup(Key, L, Val).
lookup(Key, node(_, _, _, R), Val) :-
    lookup(Key, R, Val).

% Usage:
% ?- build([2-3, 3-5, 5-1], Map), lookup(3, Map, V).
% V = 5

keys/2 and values/2 — Extract All Keys or Values

Possible Session 3 variant: “list all keys in sorted order.”

% Inorder traversal gives sorted keys
keys(empty, []).
keys(node(K, _, L, R), Keys) :-
    keys(L, LKeys),
    keys(R, RKeys),
    append(LKeys, [K | RKeys], Keys).

% Values in key-order
values(empty, []).
values(node(_, V, L, R), Vals) :-
    values(L, LVals),
    values(R, RVals),
    append(LVals, [V | RVals], Vals).

delete/3 — Remove a Key (Harder Variant)

This is the hardest BST operation. If Session 3 asks for it, here’s the recipe:

% Key not found
delete(_, empty, empty).

% Found: no children (leaf)
delete(Key, node(Key, _, empty, empty), empty) :- !.

% Found: only right child
delete(Key, node(Key, _, empty, R), R) :- !.

% Found: only left child
delete(Key, node(Key, _, L, empty), L) :- !.

% Found: two children -- replace with inorder successor
delete(Key, node(Key, _, L, R), node(SK, SV, L, NewR)) :-
    min_node(R, SK, SV),
    delete(SK, R, NewR).

% Key smaller: go left
delete(Key, node(K, V, L, R), node(K, V, NewL, R)) :-
    Key < K, !, delete(Key, L, NewL).

% Key larger: go right
delete(Key, node(K, V, L, R), node(K, V, L, NewR)) :-
    delete(Key, R, NewR).

% Helper: find minimum (leftmost) node
min_node(node(K, V, empty, _), K, V) :- !.
min_node(node(_, _, L, _), K, V) :- min_node(L, K, V).

Key-Value Map BST Recipe

node(Key, Value, Left, Right) / empty — the representation
put/4 — 4 clauses: empty, update existing, go left, go right
build/2 — fold a list of Key-Val pairs with put
lookup/3 — same as search but returns the value
keys/2 — inorder traversal collecting keys
delete/3 — handle leaf, one child, two children (use inorder successor)

Try It — Copy & Test

% === Save as bst_map.pl ===
put(Key, Val, empty, node(Key, Val, empty, empty)).
put(Key, Val, node(Key, _, L, R), node(Key, Val, L, R)) :- !.
put(Key, Val, node(K, V, L, R), node(K, V, NewL, R)) :-
    Key < K, !, put(Key, Val, L, NewL).
put(Key, Val, node(K, V, L, R), node(K, V, L, NewR)) :-
    put(Key, Val, R, NewR).

build(Pairs, Map) :- build(Pairs, empty, Map).
build([], Map, Map).
build([Key-Val | Rest], Acc, Map) :-
    put(Key, Val, Acc, NewAcc),
    build(Rest, NewAcc, Map).

lookup(Key, node(Key, Val, _, _), Val) :- !.
lookup(Key, node(K, _, L, _), Val) :-
    Key < K, !, lookup(Key, L, Val).
lookup(Key, node(_, _, _, R), Val) :-
    lookup(Key, R, Val).

keys(empty, []).
keys(node(K, _, L, R), Keys) :-
    keys(L, LKeys),
    keys(R, RKeys),
    append(LKeys, [K | RKeys], Keys).

values(empty, []).
values(node(_, V, L, R), Vals) :-
    values(L, LVals),
    values(R, RVals),
    append(LVals, [V | RVals], Vals).

% === Test in SWI-Prolog ===
% $ swipl bst_map.pl

?- build([2-3, 3-5, 5-1], Map), lookup(3, Map, V).
   V = 5.

?- build([2-3, 3-5, 5-1], Map), put(2, 99, Map, Updated), lookup(2, Updated, V).
   V = 99.

?- build([4-10, 2-20, 6-30], Map), keys(Map, Ks).
   Ks = [2, 4, 6].

?- put(1, hello, empty, T).
   T = node(1, hello, empty, empty).

6

Tree Traversals (Inorder, Preorder, Postorder)

Collecting node values in different orders

Inorder Traversal (Left, Value, Right)

Inorder traversal visits the left subtree, then the current node, then the right subtree. For a BST, this produces a sorted list -- which makes it extremely useful for verification and for "sort a list" style exam problems.

inorder(nil, []).
inorder(node(V, L, R), Result) :-
    inorder(L, LeftList),
    inorder(R, RightList),
    append(LeftList, [V|RightList], Result).

The trick is in the append call: we concatenate the left list, then the current value V prepended to the right list. This places V between the left and right results, which is exactly "in-order."

Preorder Traversal (Value, Left, Right)

preorder(nil, []).
preorder(node(V, L, R), Result) :-
    preorder(L, LeftList),
    preorder(R, RightList),
    append([V|LeftList], RightList, Result).

The value comes first: [V|LeftList] places V at the front of the left results, then the right results are appended after. Preorder is useful for copying or serializing a tree because it preserves the tree structure.

Postorder Traversal (Left, Right, Value)

postorder(nil, []).
postorder(node(V, L, R), Result) :-
    postorder(L, LeftList),
    postorder(R, RightList),
    append(LeftList, RightList, Temp),
    append(Temp, [V], Result).

The value comes last. We combine left and right results first, then append the current value at the end. Postorder is the order you would use to safely delete all nodes (children before parent).

Traversal Summary

Inorder (LVR): produces a sorted list for BSTs. Used for sorting and verification.
Preorder (VLR): root first. Used for copying/serializing the tree.
Postorder (LRV): root last. Used for deletion and expression evaluation.
All three share the same structure: nil base case, recurse L and R, combine differently.

Mnemonic: Where does V go?

The name tells you where V goes. IN-order = V is IN the middle (between L and R). PRE-order = V is at the PRE-start (before L and R). POST-order = V is POST-poned to the end (after L and R).

Trace: inorder on tree node(5, node(3, node(1,nil,nil), node(4,nil,nil)), node(7,nil,nil))

inorder(node(5, ...)): recurse left on node(3, ...)
  inorder(node(3, ...)): recurse left on node(1, nil, nil)
    inorder(node(1, nil, nil)): left=[], right=[], Result=[1]
    inorder(node(4, nil, nil)): left=[], right=[], Result=[4]
  LeftList=[1], RightList=[4], append([1], [3|[4]]) = [1,3,4]
  inorder(node(7, nil, nil)): left=[], right=[], Result=[7]
LeftList=[1,3,4], RightList=[7], append([1,3,4], [5|[7]]) = [1,3,4,5,7]

Try It — Copy & Test

% === Save as traversals.pl ===
bst_insert(X, nil, node(X, nil, nil)).
bst_insert(X, node(V, L, R), node(V, NewL, R)) :-
    X < V, !,
    bst_insert(X, L, NewL).
bst_insert(X, node(V, L, R), node(V, L, NewR)) :-
    bst_insert(X, R, NewR).

bst_build(List, Tree) :- bst_build(List, nil, Tree).
bst_build([], Tree, Tree).
bst_build([H|T], Acc, Tree) :-
    bst_insert(H, Acc, NewAcc),
    bst_build(T, NewAcc, Tree).

inorder(nil, []).
inorder(node(V, L, R), Result) :-
    inorder(L, LeftList),
    inorder(R, RightList),
    append(LeftList, [V|RightList], Result).

preorder(nil, []).
preorder(node(V, L, R), Result) :-
    preorder(L, LeftList),
    preorder(R, RightList),
    append([V|LeftList], RightList, Result).

postorder(nil, []).
postorder(node(V, L, R), Result) :-
    postorder(L, LeftList),
    postorder(R, RightList),
    append(LeftList, RightList, Temp),
    append(Temp, [V], Result).

% === Test in SWI-Prolog ===
% $ swipl traversals.pl

?- bst_build([5,3,7,1,4,6,8], T), inorder(T, L).
   L = [1, 3, 4, 5, 6, 7, 8].

?- bst_build([5,3,7,1,4,6,8], T), preorder(T, L).
   L = [5, 3, 1, 4, 7, 6, 8].

?- bst_build([5,3,7,1,4,6,8], T), postorder(T, L).
   L = [1, 4, 3, 6, 8, 7, 5].

7

Tree Height & Size

Measuring tree properties with the universal tree template

Tree Height

The height of a tree is the length of the longest path from root to a leaf. An empty tree has height 0. A single node has height 1.

tree_height(nil, 0).
tree_height(node(_, L, R), H) :-
    tree_height(L, HL),
    tree_height(R, HR),
    H is max(HL, HR) + 1.

Tree Size (Node Count)

The size of a tree is the total number of nodes. Same recursive structure, different combining step.

tree_size(nil, 0).
tree_size(node(_, L, R), S) :-
    tree_size(L, SL),
    tree_size(R, SR),
    S is SL + SR + 1.

Notice the identical structure of both predicates. They follow what we can call the Universal Tree Template:

% The Universal Tree Template
tree_op(nil, <base_value>).
tree_op(node(_, L, R), Result) :-
    tree_op(L, LeftResult),
    tree_op(R, RightResult),
    Result is <combine LeftResult and RightResult>.

The Universal Tree Template

Base case: nil returns some base value (0 for height, 0 for size, [] for traversals)
Recursive case: recurse on L and R, then combine the results
Height: combine = max(HL, HR) + 1
Size: combine = SL + SR + 1
Inorder: combine = append(LeftList, [V|RightList], Result)
Once you see this template, you can write any tree predicate in seconds

Quick Reference Table

Predicate	nil returns	Combine Step
tree_height	0	`max(HL, HR) + 1`
tree_size	0	`SL + SR + 1`
tree_sum	0	`SL + SR + V`
tree_min	(no nil case)	`min(V, min(ML, MR))`
inorder	[]	`append(L, [V\|R])`
mirror	nil	`node(V, MR, ML)` (swap)

Try It — Copy & Test

% === Save as height_size.pl ===
bst_insert(X, nil, node(X, nil, nil)).
bst_insert(X, node(V, L, R), node(V, NewL, R)) :-
    X < V, !,
    bst_insert(X, L, NewL).
bst_insert(X, node(V, L, R), node(V, L, NewR)) :-
    bst_insert(X, R, NewR).

bst_build(List, Tree) :- bst_build(List, nil, Tree).
bst_build([], Tree, Tree).
bst_build([H|T], Acc, Tree) :-
    bst_insert(H, Acc, NewAcc),
    bst_build(T, NewAcc, Tree).

tree_height(nil, 0).
tree_height(node(_, L, R), H) :-
    tree_height(L, HL),
    tree_height(R, HR),
    H is max(HL, HR) + 1.

tree_size(nil, 0).
tree_size(node(_, L, R), S) :-
    tree_size(L, SL),
    tree_size(R, SR),
    S is SL + SR + 1.

% === Test in SWI-Prolog ===
% $ swipl height_size.pl

?- bst_build([5,3,7,1,4], T), tree_height(T, H).
   H = 3.

?- tree_height(nil, H).
   H = 0.

?- bst_build([5,3,7,1,4], T), tree_size(T, S).
   S = 5.

8

Mirror & Count

Transforming and querying trees

Mirror (Swap Left and Right Children)

Mirroring a binary tree swaps the left and right subtrees at every node, recursively. The result is the "reflection" of the original tree.

mirror(nil, nil).
mirror(node(V, L, R), node(V, MR, ML)) :-
    mirror(L, ML),
    mirror(R, MR).

The key insight is in the output term: node(V, MR, ML) -- the mirrored left child becomes the right child of the result, and the mirrored right child becomes the left child. The value V stays the same.

Trace: mirror(node(5, node(3, node(1,nil,nil), nil), node(7, nil, nil)), Result)

mirror(node(5, ...)): recurse on L=node(3,...) and R=node(7,...)
  mirror(node(3, node(1,nil,nil), nil)):
    mirror(node(1,nil,nil)) = node(1,nil,nil) [ML]
    mirror(nil) = nil [MR]
    Result = node(3, nil, node(1,nil,nil)) [swapped: MR=nil goes left, ML=node(1,...) goes right]
  mirror(node(7, nil, nil)):
    Result = node(7, nil, nil) [already symmetric]
Final: node(5, node(7,nil,nil), node(3, nil, node(1,nil,nil)))

Count Nodes Satisfying a Predicate

A higher-order predicate that counts how many nodes in the tree satisfy some condition. Uses call/2 to invoke the predicate on each node's value.

count_if(_, nil, 0).
count_if(Pred, node(V, L, R), Count) :-
    count_if(Pred, L, CL),
    count_if(Pred, R, CR),
    (call(Pred, V) ->
        Count is CL + CR + 1
    ;
        Count is CL + CR
    ).

The ( Condition -> Then ; Else ) construct is Prolog's if-then-else. If call(Pred, V) succeeds, we add 1 to the count; otherwise we don't.

Usage Example: Count Even Nodes

% Define the predicate to check
is_even(X) :- X mod 2 =:= 0.

% Count even nodes in a tree
?- bst_build([5,3,7,2,4,6,8], T), count_if(is_even, T, Count).
Count = 4.   % nodes 2, 4, 6, 8 are even

Higher-Order Tree Predicates

call(Pred, V) invokes Pred with argument V -- this is how Prolog does "pass a function"
The if-then-else (Cond -> Then ; Else) is the cleanest way to handle conditional logic
You can write map_tree, filter_tree, fold_tree etc. using this same higher-order pattern
On the exam, you may need to count even/odd nodes, positive nodes, nodes greater than a threshold, etc.

Try It — Copy & Test

% === Save as mirror_count.pl ===
bst_insert(X, nil, node(X, nil, nil)).
bst_insert(X, node(V, L, R), node(V, NewL, R)) :-
    X < V, !,
    bst_insert(X, L, NewL).
bst_insert(X, node(V, L, R), node(V, L, NewR)) :-
    bst_insert(X, R, NewR).

bst_build(List, Tree) :- bst_build(List, nil, Tree).
bst_build([], Tree, Tree).
bst_build([H|T], Acc, Tree) :-
    bst_insert(H, Acc, NewAcc),
    bst_build(T, NewAcc, Tree).

inorder(nil, []).
inorder(node(V, L, R), Result) :-
    inorder(L, LeftList),
    inorder(R, RightList),
    append(LeftList, [V|RightList], Result).

mirror(nil, nil).
mirror(node(V, L, R), node(V, MR, ML)) :-
    mirror(L, ML),
    mirror(R, MR).

count_if(_, nil, 0).
count_if(Pred, node(V, L, R), Count) :-
    count_if(Pred, L, CL),
    count_if(Pred, R, CR),
    (call(Pred, V) ->
        Count is CL + CR + 1
    ;
        Count is CL + CR
    ).

is_greater_than_4(X) :- X > 4.

% === Test in SWI-Prolog ===
% $ swipl mirror_count.pl

?- bst_build([5,3,7], T), mirror(T, M), inorder(M, L).
   L = [7, 5, 3].

?- mirror(nil, M).
   M = nil.

?- bst_build([5,3,7,2,4,6,8], T), count_if(is_greater_than_4, T, C).
   C = 4.

9

DFS & BFS on Graphs

Graph traversal using stack (DFS) and queue (BFS)

Graph Representation

Graphs in Prolog are typically represented as adjacency list facts. Each fact states which nodes are reachable from a given node:

adj(a, [b, c]).
adj(b, [d]).
adj(c, []).
adj(d, []).

This says: from a you can reach b and c; from b you can reach d; c and d have no outgoing edges.

Depth-First Search (DFS)

DFS explores as deep as possible before backtracking. It uses a stack (list where we add and remove from the front) and a visited list to avoid cycles.

dfs(Start, Visited) :-
    dfs([Start], [], Visited).

% Base case: stack is empty, we are done
dfs([], Visited, Visited).

% Skip nodes we have already seen
dfs([Node|Stack], Seen, Visited) :-
    member(Node, Seen), !,
    dfs(Stack, Seen, Visited).

% Process unseen node: get neighbors, push onto stack
dfs([Node|Stack], Seen, Visited) :-
    (adj(Node, Neighbors) -> true ; Neighbors = []),
    append(Neighbors, Stack, NewStack),
    dfs(NewStack, [Node|Seen], Visited).

Breadth-First Search (BFS)

BFS explores all nodes at distance 1 before distance 2 before distance 3, etc. It uses a queue (list where we add at the back and remove from the front).

bfs(Start, Visited) :-
    bfs([Start], [], Visited).

% Base case: queue is empty, we are done
bfs([], Visited, Visited).

% Skip nodes we have already seen
bfs([Node|Queue], Seen, Visited) :-
    member(Node, Seen), !,
    bfs(Queue, Seen, Visited).

% Process unseen node: get neighbors, enqueue at back
bfs([Node|Queue], Seen, Visited) :-
    (adj(Node, Neighbors) -> true ; Neighbors = []),
    append(Queue, Neighbors, NewQueue),
    bfs(NewQueue, [Node|Seen], Visited).

DFS is like exploring a maze -- you go as deep as possible down one corridor before backtracking. BFS is like a ripple in water -- you explore everything at distance 1 before distance 2, expanding outward in concentric circles.

The only difference between DFS and BFS in the code above is one line:

DFS: append(Neighbors, Stack, NewStack) -- neighbors go to the front (stack push)
BFS: append(Queue, Neighbors, NewQueue) -- neighbors go to the back (queue enqueue)

This single change completely alters the traversal order. Memorize this difference.

DFS vs BFS Side by Side

Property	DFS	BFS
Data structure	Stack (LIFO)	Queue (FIFO)
Neighbors added to	Front of list	Back of list
append call	`append(Neighbors, Stack, ...)`	`append(Queue, Neighbors, ...)`
Explores	Deep first	Wide first
Finds shortest path?	No	Yes (unweighted)

Trace: DFS starting from a (adj(a,[b,c]), adj(b,[d]), adj(c,[]), adj(d,[]))

Step 1: Stack=[a], Seen=[]. Process a. Neighbors=[b,c]. NewStack=[b,c]. Seen=[a].
Step 2: Stack=[b,c], Seen=[a]. Process b. Neighbors=[d]. NewStack=[d,c]. Seen=[b,a].
Step 3: Stack=[d,c], Seen=[b,a]. Process d. Neighbors=[]. NewStack=[c]. Seen=[d,b,a].
Step 4: Stack=[c], Seen=[d,b,a]. Process c. Neighbors=[]. NewStack=[]. Seen=[c,d,b,a].
Step 5: Stack=[], done. Visited = [c,d,b,a].
DFS order: a, b, d, c (deep into b-d before visiting c)

Trace: BFS starting from a (same graph)

Step 1: Queue=[a], Seen=[]. Process a. Neighbors=[b,c]. NewQueue=[b,c]. Seen=[a].
Step 2: Queue=[b,c], Seen=[a]. Process b. Neighbors=[d]. NewQueue=[c,d]. Seen=[b,a].
Step 3: Queue=[c,d], Seen=[b,a]. Process c. Neighbors=[]. NewQueue=[d]. Seen=[c,b,a].
Step 4: Queue=[d], Seen=[c,b,a]. Process d. Neighbors=[]. NewQueue=[]. Seen=[d,c,b,a].
Step 5: Queue=[], done. Visited = [d,c,b,a].
BFS order: a, b, c, d (both neighbors of a before going deeper)

Graph Traversal Checklist

Always maintain a "Seen" list to avoid infinite loops in cyclic graphs
Use member(Node, Seen) to check if already visited
The cut after member(Node, Seen) prevents re-processing
(adj(Node, Neighbors) -> true ; Neighbors = []) handles nodes with no adj/2 fact
The visited list is built in reverse order -- reverse it at the end if order matters

Try It — Copy & Test

% === Save as graph.pl ===
adj(a, [b, c]).
adj(b, [d]).
adj(c, []).
adj(d, []).

dfs(Start, Visited) :-
    dfs([Start], [], Visited).
dfs([], Visited, Visited).
dfs([Node|Stack], Seen, Visited) :-
    member(Node, Seen), !,
    dfs(Stack, Seen, Visited).
dfs([Node|Stack], Seen, Visited) :-
    (adj(Node, Neighbors) -> true ; Neighbors = []),
    append(Neighbors, Stack, NewStack),
    dfs(NewStack, [Node|Seen], Visited).

bfs(Start, Visited) :-
    bfs([Start], [], Visited).
bfs([], Visited, Visited).
bfs([Node|Queue], Seen, Visited) :-
    member(Node, Seen), !,
    bfs(Queue, Seen, Visited).
bfs([Node|Queue], Seen, Visited) :-
    (adj(Node, Neighbors) -> true ; Neighbors = []),
    append(Queue, Neighbors, NewQueue),
    bfs(NewQueue, [Node|Seen], Visited).

% === Test in SWI-Prolog ===
% $ swipl graph.pl

?- dfs(a, Visited).
   Visited = [c, d, b, a].
% (reversed visit order: a, b, d, c)

?- bfs(a, Visited).
   Visited = [d, c, b, a].
% (reversed visit order: a, b, c, d)

?- dfs(d, Visited).
   Visited = [d].

10

Complete DOMjudge Example

Full exam-style problem with I/O, BST build, and inorder traversal

Problem: Read Numbers, Build BST, Print Sorted

Input: A single line of space-separated integers.
Output: The integers sorted in ascending order, space-separated on one line.

Sample Input

5 3 7 1 4 6 8

Sample Output

1 3 4 5 6 7 8

Complete Solution

:- use_module(library(readutil)).

% ===== I/O =====
main :-
    read_line_to_string(user_input, Line),
    split_string(Line, " ", " ", Tokens),
    maplist(number_codes_wrapper, Tokens, Nums),
    bst_build(Nums, Tree),
    inorder(Tree, Sorted),
    print_list(Sorted).

% Convert string token to number
number_codes_wrapper(Token, Num) :-
    atom_string(A, Token),
    atom_number(A, Num).

% ===== BST Insert =====
bst_insert(X, nil, node(X, nil, nil)).
bst_insert(X, node(V, L, R), node(V, NewL, R)) :-
    X < V, !,
    bst_insert(X, L, NewL).
bst_insert(X, node(V, L, R), node(V, L, NewR)) :-
    bst_insert(X, R, NewR).

% ===== BST Build from List =====
bst_build(List, Tree) :- bst_build(List, nil, Tree).
bst_build([], Tree, Tree).
bst_build([H|T], Acc, Tree) :-
    bst_insert(H, Acc, NewAcc),
    bst_build(T, NewAcc, Tree).

% ===== Inorder Traversal =====
inorder(nil, []).
inorder(node(V, L, R), Result) :-
    inorder(L, LeftList),
    inorder(R, RightList),
    append(LeftList, [V|RightList], Result).

% ===== Output =====
print_list([]) :- nl.
print_list([X]) :- write(X), nl.
print_list([X|Xs]) :- write(X), write(' '), print_list(Xs).

% Entry point for DOMjudge
:- initialization(main).

DOMjudge I/O Pattern

read_line_to_string(user_input, Line) reads one line as a string
split_string(Line, " ", " ", Tokens) splits on spaces, trims spaces
Convert tokens to numbers using atom_string + atom_number
:- initialization(main). makes SWI-Prolog run main/0 on startup
Always end output with nl (newline) -- DOMjudge is strict about trailing newlines

If DOMjudge uses SWI-Prolog, the :- initialization(main). directive is what makes your program actually execute. Without it, loading the file just defines predicates but runs nothing. Some setups use :- main. instead -- check your local environment.

Try It — Run Locally

% === Save the complete program above as tree_sort.pl ===
% === Create input.txt with: ===
% 5 3 7 1 4 6 8

% === Run: ===
% $ swipl tree_sort.pl < input.txt
1 3 4 5 6 7 8

% === Or test interactively: ===
% $ swipl
% ?- consult('tree_sort.pl').
% Then type: 5 3 7 1 4 6 8 [Enter]

11

Practice Problems

Six exam-style problems with full solutions

Problem 1: Build BST + Inorder

Read a list of integers from standard input (one line, space-separated). Build a BST by inserting elements left to right. Print the inorder traversal (which should be a sorted list) as a single space-separated line.

Sample Input

5 3 7 1 4 6 8

Expected Output

1 3 4 5 6 7 8

Show Solution

:- use_module(library(readutil)).

main :-
    read_line_to_string(user_input, Line),
    split_string(Line, " ", " ", Tokens),
    maplist(to_number, Tokens, Nums),
    bst_build(Nums, Tree),
    inorder(Tree, Sorted),
    print_list(Sorted).

to_number(Token, Num) :-
    atom_string(A, Token),
    atom_number(A, Num).

bst_insert(X, nil, node(X, nil, nil)).
bst_insert(X, node(V, L, R), node(V, NewL, R)) :-
    X < V, !, bst_insert(X, L, NewL).
bst_insert(X, node(V, L, R), node(V, L, NewR)) :-
    bst_insert(X, R, NewR).

bst_build(List, Tree) :- bst_build(List, nil, Tree).
bst_build([], T, T).
bst_build([H|T], Acc, Tree) :-
    bst_insert(H, Acc, NewAcc),
    bst_build(T, NewAcc, Tree).

inorder(nil, []).
inorder(node(V, L, R), Result) :-
    inorder(L, LeftList),
    inorder(R, RightList),
    append(LeftList, [V|RightList], Result).

print_list([]) :- nl.
print_list([X]) :- write(X), nl.
print_list([X|Xs]) :- write(X), write(' '), print_list(Xs).

:- initialization(main).

This is the same as the DOMjudge example in Section 9. The core idea: build tree with accumulator, extract sorted list with inorder, print with spaces.

Problem 2: BST Search

Given a BST built from the list [5, 3, 7, 1, 4], write a predicate bst_search/2 that succeeds if an element exists in the tree and fails otherwise.

Test Cases

% Build the tree first
?- bst_build([5,3,7,1,4], T), bst_search(4, T).
true.

?- bst_build([5,3,7,1,4], T), bst_search(6, T).
false.

?- bst_build([5,3,7,1,4], T), bst_search(5, T).
true.   % root element

?- bst_build([5,3,7,1,4], T), bst_search(1, T).
true.   % leftmost leaf

Show Solution

% Found: value at root matches search target
bst_search(X, node(X, _, _)).

% Search left: target is smaller than root
bst_search(X, node(V, L, _)) :-
    X < V,
    bst_search(X, L).

% Search right: target is greater than or equal to root
bst_search(X, node(V, _, R)) :-
    X >= V,
    bst_search(X, R).

Why no nil clause? If we reach nil, none of the three clauses match (they all require node(...)), so the predicate fails. Failure = "not found." This is the natural Prolog way to handle the not-found case.

Why X >= V in clause 3? Our bst_insert puts equal elements to the right (clause 3 of insert fires when X is not less than V). So search must go right for equal values too. If your insert sends duplicates left, adjust accordingly.

Problem 3: Tree Height

Read a list of integers from standard input, build a BST, and print its height. The height of an empty tree is 0. The height of a single-node tree is 1.

Sample Input

3 1 4 1 5 9 2 6

Expected Output

Explanation: Inserting [3,1,4,1,5,9,2,6] produces this tree (duplicates go right):

/*
           3
          / \
         1   4
          \   \
           1   5
          /     \
         (nil)   9
                / \
               6  (nil)

   Height: 3 -> 4 -> 5 -> 9 -> 6 is NOT a path (must go root to leaf).
   Longest root-to-leaf: 3 -> 4 -> 5 -> 9 -> 6 = 5 levels deep.
   Actually let us trace carefully:
   Insert 3: node(3, nil, nil)                           height 1
   Insert 1: node(3, node(1,nil,nil), nil)               height 2
   Insert 4: node(3, node(1,...), node(4,nil,nil))        height 2
   Insert 1: 1 >= 1, goes right of first 1               height 3
   Insert 5: goes right of 4                              height 3
   Insert 9: goes right of 5                              height 4
   Insert 2: goes right of second 1                       height 4
   Insert 6: goes left of 9                               height 5
*/

Show Solution

:- use_module(library(readutil)).

main :-
    read_line_to_string(user_input, Line),
    split_string(Line, " ", " ", Tokens),
    maplist(to_number, Tokens, Nums),
    bst_build(Nums, Tree),
    tree_height(Tree, H),
    write(H), nl.

to_number(Token, Num) :-
    atom_string(A, Token),
    atom_number(A, Num).

bst_insert(X, nil, node(X, nil, nil)).
bst_insert(X, node(V, L, R), node(V, NewL, R)) :-
    X < V, !, bst_insert(X, L, NewL).
bst_insert(X, node(V, L, R), node(V, L, NewR)) :-
    bst_insert(X, R, NewR).

bst_build(List, Tree) :- bst_build(List, nil, Tree).
bst_build([], T, T).
bst_build([H|T], Acc, Tree) :-
    bst_insert(H, Acc, NewAcc),
    bst_build(T, NewAcc, Tree).

tree_height(nil, 0).
tree_height(node(_, L, R), H) :-
    tree_height(L, HL),
    tree_height(R, HR),
    H is max(HL, HR) + 1.

:- initialization(main).

The height predicate follows the Universal Tree Template. The key combining step is max(HL, HR) + 1 -- take the taller subtree and add 1 for the current node.

Problem 4: Mirror a Binary Tree

Write mirror/2 that produces the mirror image of a binary tree. Then verify: the inorder traversal of the mirrored tree should be the reverse of the inorder traversal of the original tree.

Test Case

?- bst_build([5,3,7,1,4], T),
   inorder(T, Original),
   mirror(T, M),
   inorder(M, Mirrored),
   reverse(Original, Mirrored).
T = node(5, node(3, node(1,nil,nil), node(4,nil,nil)), node(7,nil,nil)),
Original = [1, 3, 4, 5, 7],
Mirrored = [7, 5, 4, 3, 1].

Show Solution

mirror(nil, nil).
mirror(node(V, L, R), node(V, MR, ML)) :-
    mirror(L, ML),
    mirror(R, MR).

% Verification predicate
verify_mirror(List) :-
    bst_build(List, T),
    inorder(T, Original),
    mirror(T, M),
    inorder(M, Mirrored),
    reverse(Original, Mirrored),
    write('Original inorder: '), write(Original), nl,
    write('Mirrored inorder: '), write(Mirrored), nl,
    write('Reverse matches: true'), nl.

Why does this work? Inorder traversal visits Left-Value-Right. Mirroring swaps left and right at every level. So the mirrored inorder visits what was originally Right-Value-Left, which is exactly the reverse of Left-Value-Right.

This property holds for any binary tree, not just BSTs. It is a good sanity check: if reverse(Original, Mirrored) fails, your mirror predicate has a bug.

Problem 5: Count Even Nodes

Read a list of integers, build a BST, and print how many nodes have even values.

Sample Input

5 3 7 2 4 6 8

Expected Output

Explanation: The even values in the tree are 2, 4, 6, 8 -- that is 4 nodes.

Show Solution

Approach A: Using count_if with a predicate

:- use_module(library(readutil)).

main :-
    read_line_to_string(user_input, Line),
    split_string(Line, " ", " ", Tokens),
    maplist(to_number, Tokens, Nums),
    bst_build(Nums, Tree),
    count_if(is_even, Tree, Count),
    write(Count), nl.

to_number(Token, Num) :-
    atom_string(A, Token),
    atom_number(A, Num).

is_even(X) :- X mod 2 =:= 0.

count_if(_, nil, 0).
count_if(Pred, node(V, L, R), Count) :-
    count_if(Pred, L, CL),
    count_if(Pred, R, CR),
    (call(Pred, V) ->
        Count is CL + CR + 1
    ;
        Count is CL + CR
    ).

% Include bst_insert/3 and bst_build/3 from above
bst_insert(X, nil, node(X, nil, nil)).
bst_insert(X, node(V, L, R), node(V, NewL, R)) :-
    X < V, !, bst_insert(X, L, NewL).
bst_insert(X, node(V, L, R), node(V, L, NewR)) :-
    bst_insert(X, R, NewR).

bst_build(List, Tree) :- bst_build(List, nil, Tree).
bst_build([], T, T).
bst_build([H|T], Acc, Tree) :-
    bst_insert(H, Acc, NewAcc),
    bst_build(T, NewAcc, Tree).

:- initialization(main).

Approach B: Simpler, without higher-order predicates

% If you find call/2 confusing, just inline the check:
count_even(nil, 0).
count_even(node(V, L, R), Count) :-
    count_even(L, CL),
    count_even(R, CR),
    (V mod 2 =:= 0 ->
        Count is CL + CR + 1
    ;
        Count is CL + CR
    ).

Both approaches are correct. Approach A is more general (change is_even to any predicate). Approach B is simpler to write under exam pressure.

Problem 6: DFS Traversal

Given the following adjacency list, find all reachable nodes from a using depth-first search. Print the nodes in the order they were visited.

adj(a, [b, c]).
adj(b, [d, e]).
adj(c, [f]).
adj(d, []).
adj(e, []).
adj(f, []).

The graph looks like:

/*
    a
   / \
  b   c
 / \   \
d   e   f
*/

Expected Output (DFS order)

a b d e c f

(DFS goes deep: a, then b, then d (dead end), then e (dead end), back to a's second child c, then f.)

Show Solution

% Graph facts
adj(a, [b, c]).
adj(b, [d, e]).
adj(c, [f]).
adj(d, []).
adj(e, []).
adj(f, []).

% DFS implementation
dfs(Start, Visited) :-
    dfs([Start], [], Visited).

dfs([], Visited, Visited).

dfs([Node|Stack], Seen, Visited) :-
    member(Node, Seen), !,
    dfs(Stack, Seen, Visited).

dfs([Node|Stack], Seen, Visited) :-
    (adj(Node, Neighbors) -> true ; Neighbors = []),
    append(Neighbors, Stack, NewStack),
    dfs(NewStack, [Node|Seen], Visited).

% Main: run DFS and print visited nodes in order
main :-
    dfs(a, VisitedReversed),
    reverse(VisitedReversed, Visited),
    print_list(Visited).

print_list([]) :- nl.
print_list([X]) :- write(X), nl.
print_list([X|Xs]) :- write(X), write(' '), print_list(Xs).

:- initialization(main).

Full Trace

Step 1: Stack=[a], Seen=[]. a not in Seen. adj(a,[b,c]). append([b,c],[])=[b,c]. Seen=[a].
Step 2: Stack=[b,c], Seen=[a]. b not in Seen. adj(b,[d,e]). append([d,e],[c])=[d,e,c]. Seen=[b,a].
Step 3: Stack=[d,e,c], Seen=[b,a]. d not in Seen. adj(d,[]). append([],[e,c])=[e,c]. Seen=[d,b,a].
Step 4: Stack=[e,c], Seen=[d,b,a]. e not in Seen. adj(e,[]). append([],[c])=[c]. Seen=[e,d,b,a].
Step 5: Stack=[c], Seen=[e,d,b,a]. c not in Seen. adj(c,[f]). append([f],[])=[f]. Seen=[c,e,d,b,a].
Step 6: Stack=[f], Seen=[c,e,d,b,a]. f not in Seen. adj(f,[]). append([],[])=[]. Seen=[f,c,e,d,b,a].
Step 7: Stack=[], done. VisitedReversed=[f,c,e,d,b,a].
Reversed: [a,b,d,e,c,f] -- this is the DFS visit order.

Important: The Seen list is built in reverse order (newest first), so we call reverse/2 at the end to get the actual visit order. If the problem does not care about order (just "all reachable nodes"), you can skip the reverse.

Bonus: BFS on the Same Graph

% Change ONE line: append(Queue, Neighbors, NewQueue)
bfs(Start, Visited) :-
    bfs([Start], [], Visited).

bfs([], Visited, Visited).

bfs([Node|Queue], Seen, Visited) :-
    member(Node, Seen), !,
    bfs(Queue, Seen, Visited).

bfs([Node|Queue], Seen, Visited) :-
    (adj(Node, Neighbors) -> true ; Neighbors = []),
    append(Queue, Neighbors, NewQueue),
    bfs(NewQueue, [Node|Seen], Visited).

% BFS visit order (after reverse): a, b, c, d, e, f
% All distance-1 nodes (b,c) before distance-2 nodes (d,e,f)

Problem 7: Key-Value Map Operations

Build a map from the list [4-10, 2-20, 6-30, 1-40, 3-50]. Then: (a) look up key 3, (b) update key 2 to value 99, (c) list all keys in sorted order. (Uses: put, build, lookup, keys — section 5)

% Expected:
% (a) lookup(3, Map, V) → V = 50
% (b) put(2, 99, Map, Updated), lookup(2, Updated, V2) → V2 = 99
% (c) keys(Map, Ks) → Ks = [1, 2, 3, 4, 6]

Show Solution

% Build the map
?- build([4-10, 2-20, 6-30, 1-40, 3-50], Map).

% (a) Lookup key 3
?- build([4-10, 2-20, 6-30, 1-40, 3-50], Map), lookup(3, Map, V).
V = 50

% (b) Update key 2
?- build([4-10, 2-20, 6-30, 1-40, 3-50], Map),
   put(2, 99, Map, Updated),
   lookup(2, Updated, V2).
V2 = 99

% (c) List all keys
?- build([4-10, 2-20, 6-30, 1-40, 3-50], Map), keys(Map, Ks).
Ks = [1, 2, 3, 4, 6]

The build order matters for tree shape but not for correctness. All operations work regardless of insertion order because the BST property is maintained by put.

Exam Day Checklist

Things to Memorize

Tree = nil or node(V, L, R). Every predicate has both cases.
BST insert: 3 clauses. The cut after X < V is a green cut (optional but good practice).
BST build: accumulator pattern, start with nil, insert each element from the list.
BST search: 3 clauses, no nil case (failure = not found), no output tree argument.
Traversals: In=LVR (sorted), Pre=VLR, Post=LRV. The name tells you where V goes.
Universal Tree Template: base nil, recurse L and R, combine. Works for height, size, sum, mirror, etc.
DFS vs BFS: the ONLY difference is append(Neighbors, Stack, ...) vs append(Queue, Neighbors, ...).
I/O: read_line_to_string, split_string, convert tokens to numbers, :- initialization(main).

If you can write bst_insert, bst_build, inorder, tree_height, and DFS from memory, you can solve virtually any tree/graph problem on the exam by combining these building blocks.

IO

Prolog I/O Templates — Copy-Paste Ready

Save these as .pl files. They handle stdin/stdout for DOMjudge.

Template 1: Read Two Numbers, Print Sum

The simplest possible DOMjudge program. Input: one line with two space-separated integers.

% === Save as sum.pl ===
:- initialization(main).

main :-
    read_line_to_string(user_input, Line),
    split_string(Line, " ", " \t\r\n", Parts),
    maplist(number_string, [A, B], Parts),
    Sum is A + B,
    writeln(Sum),
    halt.

% === Test ===
% $ echo "3 7" | swipl sum.pl
10

What Each Line Does

:- initialization(main). — run main automatically when file loads
read_line_to_string(user_input, Line) — read one line from stdin as a string
split_string(Line, " ", " \t\r\n", Parts) — split on spaces, trim whitespace
maplist(number_string, [A, B], Parts) — convert string tokens to numbers
writeln(Sum) — print with newline (same as write(Sum), nl)
halt — exit cleanly (some DOMjudge setups need this)

Template 2: Read a List of Numbers on One Line

Input: one line with N space-separated integers. Process them and print result.

% === Save as list_process.pl ===
:- initialization(main).

main :-
    read_line_to_string(user_input, Line),
    split_string(Line, " ", " \t\r\n", Tokens),
    maplist(to_number, Tokens, Nums),
    % === YOUR LOGIC HERE ===
    % Example: sort the list using BST
    bst_build(Nums, Tree),
    inorder(Tree, Sorted),
    print_list(Sorted),
    halt.

to_number(Token, Num) :-
    number_string(Num, Token).

% ... include your predicates here ...

print_list([]) :- nl.
print_list([X]) :- write(X), nl.
print_list([X|Xs]) :- write(X), write(' '), print_list(Xs).

% === Test ===
% $ echo "5 3 7 1 4" | swipl list_process.pl
1 3 4 5 7

Template 3: Read Multiple Lines

Input: first line is N, then N lines of data.

% === Save as multiline.pl ===
:- initialization(main).

main :-
    read_line_to_string(user_input, NStr),
    number_string(N, NStr),
    read_n_lines(N, Lines),
    % Lines is a list of strings, one per line
    maplist(writeln, Lines),
    halt.

read_n_lines(0, []) :- !.
read_n_lines(N, [Line|Rest]) :-
    N > 0,
    read_line_to_string(user_input, Line),
    N1 is N - 1,
    read_n_lines(N1, Rest).

% === Test ===
% $ printf "3\nhello\nworld\nfoo" | swipl multiline.pl
hello
world
foo

Template 4: Read Line + Single Number (Two Lines)

Input: list on line 1, single number on line 2. Common exam pattern.

% === Save as search_in_list.pl ===
:- initialization(main).

main :-
    read_line_to_string(user_input, Line1),
    read_line_to_string(user_input, Line2),
    split_string(Line1, " ", " \t\r\n", Tokens),
    maplist(to_number, Tokens, Nums),
    number_string(Target, Line2),
    % === YOUR LOGIC HERE ===
    % Example: check if Target is in BST built from Nums
    bst_build(Nums, Tree),
    (bst_search(Target, Tree) ->
        writeln("true")
    ;
        writeln("false")
    ),
    halt.

to_number(Token, Num) :-
    number_string(Num, Token).

% ... include bst_build, bst_insert, bst_search here ...

% === Test ===
% $ printf "5 3 7 1 4\n4" | swipl search_in_list.pl
true
% $ printf "5 3 7 1 4\n6" | swipl search_in_list.pl
false

Template 5: Key-Value Map from Pairs

Input: pairs like 2-3 3-5 5-1 on one line. Build a map and do operations.

% === Save as map_demo.pl ===
:- initialization(main).

main :-
    read_line_to_string(user_input, Line),
    split_string(Line, " ", " \t\r\n", Tokens),
    maplist(parse_pair, Tokens, Pairs),
    build(Pairs, Map),
    keys(Map, Ks),
    print_list(Ks),
    halt.

parse_pair(Token, Key-Val) :-
    split_string(Token, "-", "", [KStr, VStr]),
    number_string(Key, KStr),
    number_string(Val, VStr).

% ... include put, build, lookup, keys here ...

print_list([]) :- nl.
print_list([X]) :- write(X), nl.
print_list([X|Xs]) :- write(X), write(' '), print_list(Xs).

% === Test ===
% $ echo "4-10 2-20 6-30 1-40 3-50" | swipl map_demo.pl
1 2 3 4 6

Quick Reference: I/O Predicates

Predicate	What it does
`read_line_to_string(user_input, S)`	Read one line from stdin as string
`split_string(S, " ", " \t\r\n", Tokens)`	Split string on spaces, trim whitespace
`number_string(N, S)`	Convert between number and string (bidirectional)
`maplist(Pred, List)`	Apply predicate to every element
`write(X)`	Print without newline
`writeln(X)`	Print with newline
`nl`	Print just a newline
`halt`	Exit the program
`:- initialization(main).`	Run main/0 on file load

Alternate conversion: If number_string doesn’t work on your SWI-Prolog version, use:
to_number(Token, Num) :- atom_string(A, Token), atom_number(A, Num).

Table of Contents

How Prolog Represents Binary Trees

Visual Example

Pattern Matching on Trees

Try It — Copy & Test

Three-Clause Insert

Try It — Copy & Test

Accumulator-Based Construction

Try It — Copy & Test

Three-Clause Search

Try It — Copy & Test

The Map Representation

put/4 — Insert or Update a Key-Value Pair

build/2 — Build Map from a List of Pairs

lookup/3 — Find a Value by Key

keys/2 and values/2 — Extract All Keys or Values

delete/3 — Remove a Key (Harder Variant)

Try It — Copy & Test

Inorder Traversal (Left, Value, Right)

Preorder Traversal (Value, Left, Right)

Postorder Traversal (Left, Right, Value)

Try It — Copy & Test

Tree Height

Tree Size (Node Count)

Quick Reference Table

Try It — Copy & Test

Mirror (Swap Left and Right Children)

Count Nodes Satisfying a Predicate

Usage Example: Count Even Nodes

Try It — Copy & Test

Graph Representation

Depth-First Search (DFS)

Breadth-First Search (BFS)

DFS vs BFS Side by Side

Try It — Copy & Test

Problem: Read Numbers, Build BST, Print Sorted

Sample Input

Sample Output

Complete Solution

Try It — Run Locally

Problem 1: Build BST + Inorder

Sample Input

Expected Output

Problem 2: BST Search

Test Cases

Problem 3: Tree Height

Sample Input

Expected Output

Problem 4: Mirror a Binary Tree

Test Case

Problem 5: Count Even Nodes

Sample Input

Expected Output

Approach A: Using count_if with a predicate

Approach B: Simpler, without higher-order predicates

Problem 6: DFS Traversal

Expected Output (DFS order)

Bonus: BFS on the Same Graph

Problem 7: Key-Value Map Operations

Exam Day Checklist

Template 1: Read Two Numbers, Print Sum

Template 2: Read a List of Numbers on One Line

Template 3: Read Multiple Lines

Template 4: Read Line + Single Number (Two Lines)

Template 5: Key-Value Map from Pairs

Quick Reference: I/O Predicates