Demo: BST insert and traversals, step by step
On This Lesson 11 topics
Lesson Overview
This is a hands-on lesson. You already know the pieces: the BST rule, recursive insert, four traversals, and the chain problem. Here we put them into one working program, built step by step, the way you will build it in the module lab. We draw the tree by hand first, then write the code, then check the code against the drawing.
We also make one mistake on purpose: we leave out the null check in insert, run the program, read the NullPointerException, and fix it. Reading that message calmly is a skill you will use for the rest of your career.
Everything below was compiled and run with JDK 21. Use any editor or IDE you like. Menus differ between tools, so the steps use plain files and the javac and java commands in a terminal, run from the folder that holds the file. If your IDE compiles for you, the code is the same.
This lesson builds on all earlier lessons of this module, on List and Queue from the collections module, and on reading stack traces from the exceptions module.
Learning Objectives
By the end of this lesson you will be able to:
- Draw the BST that results from a sequence of inserts, one insert at a time.
- Write
Node, a recursiveinsert, and the four traversals in one program. - Reproduce the missing-
nullNullPointerException, read its message and stack trace, and fix it. - Check program output against a hand-drawn tree.
- Show the chain problem by inserting 1 to 6 in order and printing the height.
- Name which parts of the demo you will reuse in the lab.
Written Explanation
Step 1: draw the tree first
Before writing code, draw the BST for the inserts 8, 3, 10, 1, 6, 14, one value at a time. Doing this on paper first gives you something to check the program against.
| Insert | Path taken | Result |
|---|---|---|
| 8 | tree is empty | root |
| 3 | 3 < 8, go left | left child of 8 |
| 10 | 10 > 8, go right | right child of 8 |
| 1 | 1 < 8, go left; 1 < 3, go left | left child of 3 |
| 6 | 6 < 8, go left; 6 > 3, go right | right child of 3 |
| 14 | 14 > 8, go right; 14 > 10, go right | right child of 10 |
8
/ \
3 10
/ \ \
1 6 14Now predict the four traversals from the drawing, before running anything. Pre-order (node, left, right): 8 3 1 6 10 14. In-order (left, node, right): 1 3 6 8 10 14. Post-order (left, right, node): 1 6 3 14 10 8. Level-order (row by row): 8 3 10 1 6 14. The code must agree with every one of these.
Step 2: the node and a recursive insert
Create a file BstDemo.java. Start with the node and insert:
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
public class BstDemo {
static class Node {
int value;
Node left, right;
Node(int value) { this.value = value; }
}
static Node insert(Node n, int v) {
if (n == null) return new Node(v);
if (v < n.value) n.left = insert(n.left, v);
else if (v > n.value) n.right = insert(n.right, v);
return n;
}The first line of insert is the base case: an empty spot gets the new node. The method returns the root of the subtree, and the caller stores it back (n.left = insert(n.left, v)). A duplicate matches neither branch and is ignored.
Step 3 (the planned mistake): omit the base case
To see what the base case protects against, we temporarily write insert without it and call it from a main that builds the tree from a single root:
static Node insert(Node n, int v) {
if (v < n.value) n.left = insert(n.left, v); // no null check!
else if (v > n.value) n.right = insert(n.right, v);
return n;
}
public static void main(String[] args) {
Node root = new Node(8);
for (int v : new int[] {3, 10, 1, 6, 14}) root = insert(root, v);
System.out.println("done");
}It compiles without complaint, because the compiler cannot know a reference will be null at run time. Run it (compiled with javac -g, which keeps variable names for the message):
Exception in thread "main" java.lang.NullPointerException: Cannot read field "value" because "n" is null
at Broken.insert(Broken.java:9)
at Broken.insert(Broken.java:9)
at Broken.main(Broken.java:16)Read it from the top: the message says what went wrong (reading the field value of a variable n that is null). The stack trace says where: the same line of insert twice, which is the recursion, called from main. Inserting 3 goes left of 8, whose left child is null, so the recursive call receives null and reads n.value. The fix is to put if (n == null) return new Node(v); first, which is the version in Step 2.
The lesson of the mistake: in recursive tree code, ask what happens when the node is null before you write anything else.
Step 4: the three recursive traversals
With the fixed insert in place, add the traversals. They differ only in the position of out.add:
static void inOrder(Node n, List<Integer> out) {
if (n == null) return;
inOrder(n.left, out);
out.add(n.value);
inOrder(n.right, out);
}
static void preOrder(Node n, List<Integer> out) {
if (n == null) return;
out.add(n.value);
preOrder(n.left, out);
preOrder(n.right, out);
}
static void postOrder(Node n, List<Integer> out) {
if (n == null) return;
postOrder(n.left, out);
postOrder(n.right, out);
out.add(n.value);
}Step 5: level-order with a queue
Level-order uses an ArrayDeque as a queue: poll the front, visit it, offer its non-null children at the back.
static List<Integer> levelOrder(Node root) {
List<Integer> out = new ArrayList<>();
if (root == null) return out;
Queue<Node> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node n = queue.poll();
out.add(n.value);
if (n.left != null) queue.offer(n.left);
if (n.right != null) queue.offer(n.right);
}
return out;
}
static int height(Node n) {
if (n == null) return -1;
return 1 + Math.max(height(n.left), height(n.right));
}We include height from Lesson 1 for the last step.
Step 6: run it, compare, then break the shape
The main method inserts the six values, prints all four traversals and the height, then inserts 1 to 6 in order into a second tree and prints its height:
public static void main(String[] args) {
Node root = null;
for (int v : new int[] {8, 3, 10, 1, 6, 14}) root = insert(root, v);
List<Integer> in = new ArrayList<>(), pre = new ArrayList<>(), post = new ArrayList<>();
inOrder(root, in);
preOrder(root, pre);
postOrder(root, post);
System.out.println("in " + in);
System.out.println("pre " + pre);
System.out.println("post " + post);
System.out.println("level " + levelOrder(root));
System.out.println("height " + height(root));
Node chain = null;
for (int v = 1; v <= 6; v++) chain = insert(chain, v);
System.out.println("chain 1..6: height " + height(chain) + ", level " + levelOrder(chain));
}
}Compile with javac BstDemo.java and run with java BstDemo. Output:
in [1, 3, 6, 8, 10, 14]
pre [8, 3, 1, 6, 10, 14]
post [1, 6, 3, 14, 10, 8]
level [8, 3, 10, 1, 6, 14]
height 2
chain 1..6: height 5, level [1, 2, 3, 4, 5, 6]All four traversals match the predictions from Step 1, and the height is 2 as in the drawing. The last line is the problem of Lesson 4 in miniature: six sorted inserts give height 5, one node per level, so its level-order output is just 1 to 6 in a line.
Examples
Example 1: checking the code against the drawing (simple)
If your output differs from the prediction, compare the failing traversal with the drawing, node by node. A wrong in-order result usually means out.add is in the wrong place. A wrong level-order result usually means a child was queued in the wrong order, or the root was never queued. Always fix the code, never the drawing, unless the drawing's inserts were wrong.
Example 2: a different insert order (practical)
Insert 5, 2, 9, 1, 3, 7 and predict first. The tree has root 5, left child 2 (with children 1 and 3), and right child 9 whose left child is 7. Running the same traversal methods on it printed:
pre [5, 2, 1, 3, 9, 7]
in [1, 2, 3, 5, 7, 9]
post [1, 3, 2, 7, 9, 5]
level [5, 2, 9, 1, 3, 7]The in-order output is sorted again. Whatever the shape, the sorted result is the same, which you can use as a quick correctness test for any BST code: insert any values, run in-order, and check that the list is ascending.
Example 3: turning checks into a tiny test (realistic)
In the lab, "tests pass" means automated checks. A minimal version needs no framework: compare the actual output with the expected list and print a clear message.
static void check(String name, List<Integer> actual, List<Integer> expected) {
System.out.println(name + ": " + (actual.equals(expected) ? "PASS" : "FAIL " + actual));
}You would call check("in-order", in, List.of(1, 3, 6, 8, 10, 14)) for each traversal. Later modules introduce a proper test framework, but the idea is the same: write down the expected answer from your hand drawing first, then let the program prove it.
Backend Insight
- Hand-drawing before coding is real practice. Engineers sketch a data structure or a request flow before implementing it, because a drawing exposes mistakes cheaply.
- Stack traces are maps. The repeated line in the trace told us the failure was inside the recursion, and the last frame told us who started it. Backend logs contain traces like this daily.
- In-order as a test oracle. A sorted in-order result is a fast sanity check for any ordered structure, and the same idea (check an invariant after every change) is used in tests for caches, indexes, and sorted collections.
- The chain warning is production-relevant. The six-value chain is harmless; the same pattern with many sorted ids is not (Lesson 4). That is why
TreeMapis the production choice.
Common Mistakes
Mistake 1: Leaving out the null check
This is the planned mistake. The cure is the same every time: handle null first.
Mistake 2: Mixing up which traversal prints sorted values
If your sorted check fails, check that you called inOrder and not preOrder. Only in-order sorts a BST.
Mistake 3: Adding null children to the queue
In levelOrder, queue.offer(n.left) without the if would throw for a missing child, because ArrayDeque does not accept null. Check each child before queuing it.
Mistake 4: Changing the code until the output "looks right"
Predict from the drawing first. If you only tweak the code until the numbers look plausible, you can hide a real bug.
Exercises
Try each exercise yourself before opening the solutions. Use the BstDemo class from this lesson.
Level A: Foundation
A1. Draw the BST for the inserts 5, 2, 9, 1, 3, 7 and give its in-order output.
Show solution A1
A1. Root 5. Left child 2, with children 1 (left) and 3 (right). Right child 9, with left child 7. In-order: 1 2 3 5 7 9.
A2. In insert, what does the line if (n == null) return new Node(v); do, and what happens without it?
Show solution A2
A2. It is the base case: when the recursion reaches an empty spot, it creates the new node there. Without it, the first recursive call that receives null reads n.value and throws a NullPointerException, as the demo showed.
A3. What height does the tree get if you insert 1, 2, 3, 4, 5, 6, 7 in that order?
Show solution A3
A3. Height 6 (seven nodes in a chain, six links). Each new value is larger than all earlier ones and goes to the right of the last node.
Level B: Application
B1. Write static int countLeaves(Node n) using the null check first. What does it return for the tree 8, 3, 10, 1, 6, 14?
Show solution B1
B1.
static int countLeaves(Node n) {
if (n == null) return 0;
if (n.left == null && n.right == null) return 1;
return countLeaves(n.left) + countLeaves(n.right);
}It returns 3 for the demo tree (the leaves are 1, 6, and 14).
B2. Write static boolean contains(Node n, int v) and say what it returns for 14 and for 7 in that tree.
Show solution B2
B2.
static boolean contains(Node n, int v) {
if (n == null) return false;
if (v == n.value) return true;
return v < n.value ? contains(n.left, v) : contains(n.right, v);
}It returns true for 14 and false for 7 (compiled and run with JDK 21).
B3. For the tree from A1, write the pre-order, post-order, and level-order outputs.
Show solution B3
B3. Pre-order: 5 2 1 3 9 7. Post-order: 1 3 2 7 9 5. Level-order: 5 2 9 1 3 7.
Level C: Challenge
C1. Write static int kthSmallest(Node root, int k) (counting from 1) using one of the traversals. What is the third smallest value in the demo tree?
Show solution C1
C1.
static int kthSmallest(Node root, int k) {
List<Integer> in = new ArrayList<>();
inOrder(root, in);
return in.get(k - 1);
}In-order is sorted, so position k - 1 of the list is the k-th smallest. For the demo tree it returns 6. The method assumes 1 <= k <= number of nodes; otherwise get throws an IndexOutOfBoundsException.
C2. Using contains from B2 (added to BstDemo), write a small class Tree with a method boolean add(int v) that returns false when the value was already present and true when it was added. Explain the cost of your approach.
Show solution C2
C2.
static class Tree {
Node root;
boolean add(int v) {
if (BstDemo.contains(root, v)) return false;
root = BstDemo.insert(root, v);
return true;
}
}Calling add(5) twice returns true then false. It searches twice (once in contains, once in insert), so the cost is still proportional to the height, which is O(log n) on a balanced tree and O(n) on a chain. A single-pass version would make insert report whether it created a node.
Mini Challenge
Make the demo your own. Change the inserts to six numbers of your choice, draw the tree and predict the four traversals on paper, then run the program and compare. Next, change the input to six numbers in descending order and predict the height before running. Then write down in two sentences why the shapes differ.
Check your work: every predicted traversal matches the program output, the in-order list is ascending in both cases, and the descending input gives height 5.
Summary & Next Lesson
Key takeaways
- Draw the BST first and predict the traversals; then the program has something to be checked against.
- Recursive tree code starts with the
nullcheck. Without it, insert throws aNullPointerExceptionat the first empty child. - A stack trace shows the recursion as repeated frames, with the starting call at the bottom.
- Pre-, in-, and post-order differ only in where the visit goes; level-order uses a queue.
- In-order output of a BST is always ascending, which makes it a good quick test; sorted inserts give a chain.
Next lesson
This was the last lesson of the module. The module lab, "BST and task scheduler", asks you to build the BST with insert, contains, and all four traversals returning lists, to show the height problem on sorted input, and to build a scheduler on PriorityQueue.
Self-check
- What must be the first line of a recursive
insert? - What does the repeated line in the stack trace tell you?
- Which traversal gives sorted output on a BST?
- Why does
levelOrdercheckn.left != nullbeforeoffer? - What height do six sorted inserts give?
Show answers
- The base case:
if (n == null) return new Node(v);. - The failure happened inside the recursion, with the same method calling itself until it hit
null. - In-order.
ArrayDequedoes not acceptnull, and a missing child isnull.- 5 (six nodes in a chain, five links).
References
- OpenDSA (Virginia Tech): Binary Tree Traversals. It defines pre-, in-, and post-order traversal and says in-order on a BST yields ascending values.
- OpenDSA (Virginia Tech): Binary Search Trees. It describes insert as searching for the place and attaching a leaf, and says sorted insertion gives a chain of height n - 1.
- I did not fetch a source for
ArrayDequerejectingnullelements; that is a documented property of the class, so check it in the Javadoc. Every Java example above was compiled and run with JDK 21 and the output is copied from the real run.
Practice
Apply this lesson with the module's lab, exercises and quiz.
Marking a lesson complete is optional and you can undo it any time. Your progress stays in this browser.