Page 38: Master Traversal Practice Example
This page provides an advanced, asymmetrical tree structure to test your traversal skills for the
exam.
The Tree Layout:
P
/ \
F S
/\ /\
B HR Y
/ /\
G T Z
\
W
Traversal Solutions:
● In-Order (Left -> Root -> Right): Follow the left branches down first.
○ Result: B F G H P R S T W Y Z (Notice it is in perfect alphabetical order).
● Pre-Order (Root -> Left -> Right): Record each node the moment you touch it.
○ Result: P F B H G S R Y T W Z
● Post-Order (Left -> Right -> Root): Record the parent only after visiting all its children.
○ Result: B G H F R W T Z Y S P (The main root P is processed last).
Page 39: Searching & The Successor Function
● Searching Behavior: Begin at the root node. If your target value matches, you are done.
If the target is smaller, move to the left child; if it is larger, move to the right child.
Successor Logic (The Next Largest Value):
A successor is the element with the next highest value (a little bit bigger).
● Rule 1 (Right subtree exists): Go right exactly one step, then find the furthest leftmost
node in that branch.
● Rule 2 (No right subtree): Trace upward to find the lowest ancestor whose left child is
also an ancestor of your target node.
Exam Tree Examples:
Using the tree at the bottom of the page:
● Successor of 15 is 17 (Go right to 18, then left to 17).
● Successor of 7 is 9 (Go right to 13, then left to 9).
● Successor of 13 is 15 (It has no right subtree; tracing up, 15 is the lowest ancestor that
contains 13 in its left branch).
Page 40: The Predecessor Function
A predecessor is the element with the next lowest value (a little bit smaller).
Predecessor Logic:
● Rule 1 (Left subtree exists): Go left exactly one step, then find the furthest rightmost
node in that branch.
● Rule 2 (No left subtree): Trace upward to find the lowest ancestor whose right child is
also an ancestor of your target node.
Exam Tree Examples:
Using the same tree structure:
● Predecessor of 6 is 4 (Go left to 3, then right to 4).
● Predecessor of 15 is 13 (Go left to 6, then right to 7, then right to 13).
● Predecessor of 17 is 15 (It has no left subtree; tracing up, 15 is the lowest ancestor that
contains 17 in its right branch).
Page 41: Deletion Case 1 and Case 2
When you remove a node from a Binary Search Tree, you must replace it properly so the tree
still satisfies the sorting rules.
Case 1: Deleting a Leaf Node (No Children)
● Action: Disconnect and remove it directly. No other structural changes are needed.
● Example: Removing leaf node 45 leaves its parent node 40 empty on the right.
Case 2: Deleting a Node with Exactly One Child
● Action: Bypass the deleted target. Connect its single child directly up to its grandparent
node.
● Example: Removing node 20 (which has a single left child 18). Node 18 gets linked
directly up to the grandparent node 15.
Page 42: Deletion Case 3 (Two Children)
This is the most complex deletion scenario and is highly likely to appear on your exam.
Case 3: Deleting a Node with Two Distinct Children
1. Locate the target node's In-Order Successor (the smallest value in its right subtree).
2. Overwrite the value of the node you want to delete with that successor's value.
3. Delete the original successor node from the bottom of the tree (which will always be a
simple Case 1 or Case 2 deletion).
Example Walkthrough (Removing Node 15):
● Node 15 has two children (5 and 20).
● Step 1: Find the In-Order Successor of 15. Go right to 20, then left to find 18.
● Step 2: Replace the value 15 with 18.
● Step 3: The tree now temporarily has a duplicate 18 at the bottom. Go to the bottom and
delete that original leaf node 18.
You have officially reviewed your entire notebook from Page 1 to Page 42! Good luck with your
exam tomorrow—you've got this! If you want to try a quick practice quiz to lock in these rules,
just let me know.