ITC 120 › Midterm › Trees and BSTs

Trees and BSTs · Lesson 2 of 6

Binary Search Trees and BST Search

This lesson teaches:Data structureAlgorithm

A binary tree with one extra rule that tells each search to go left or right, so it can skip whole parts of the tree.

By the end, you can:

state the BST rule and tell whether a given tree follows it;
search a BST by hand and list the nodes you visit, for a value that is found and one that is not;
trace the search method in Java, and write a method that returns the search path.

You need: the Trees lesson, and scratch paper.

Part 1 · The BST rule

Keeping values in order

A guessing game

Bea is thinking of a number from 1 to 100. Migs tries to guess it. After each guess, Bea only says "too low," "too high," or "yes." Watch how Migs thinks:

A binary search tree arranges values so that every comparison works like that guess. You have met this halving idea before: in the number game in the Introduction, and you will write it in Java as binary search in the Searching lesson (final topics).

Binary search tree (BST)

A binary search tree is a binary tree where, for every node:

all values in its left subtree are smaller than its value, and
all values in its right subtree are larger than its value.

Migs never guessed randomly: he always picked the middle, so every answer threw away half. A BST works in a similar way. Each node is like a guess: smaller values go to one side, larger values to the other, so each comparison lets us skip a whole subtree. One difference: the two sides are not always the same size. A BST built from values in sorted order can even become one long chain (you will see this in BST Insertion).

At 50: everything on the left (20, 30, 40) is smaller; everything on the right (60, 70, 80) is larger. At 30: 20 is smaller, 40 is larger. At 70: 60 is smaller, 80 is larger. The rule holds at every node.

How to check one node

Walk from the node up to the root. At each ancestor, ask: am I on its left or its right? For 40: it is on the right of 30 (40 > 30 ✓) and on the left of 50 (40 < 50 ✓). So 40 must be between them: 30 < 40 < 50.

Try it on any node of Tree A. Then switch to Tree B: it looks almost the same, but one value is in the wrong place. Find it.

Check any node

Tap a node. We walk up to the root and check it against every ancestor.

Tree A is the lesson tree. Every node follows the rule. Tap any node to see why.

Walk up from 20 to the root. At each ancestor (teal), ask: which side am I on?

✓ 20 is in the left side of 30, so it must be smaller: 20 < 30? yes
✓ 20 is in the left side of 50, so it must be smaller: 20 < 50? yes

So 20 must be smaller than 30. It is. 20 follows the rule.

Walk up from 30 to the root. At each ancestor (teal), ask: which side am I on?

✓ 30 is in the left side of 50, so it must be smaller: 30 < 50? yes

So 30 must be smaller than 50. It is. 30 follows the rule.

Walk up from 40 to the root. At each ancestor (teal), ask: which side am I on?

✓ 40 is in the right side of 30, so it must be larger: 40 > 30? yes
✓ 40 is in the left side of 50, so it must be smaller: 40 < 50? yes

So 40 must be between 30 and 50. It is. 40 follows the rule.

50 is the root: it has no ancestors to check.

Walk up from 60 to the root. At each ancestor (teal), ask: which side am I on?

✓ 60 is in the left side of 70, so it must be smaller: 60 < 70? yes
✓ 60 is in the right side of 50, so it must be larger: 60 > 50? yes

So 60 must be between 50 and 70. It is. 60 follows the rule.

Walk up from 70 to the root. At each ancestor (teal), ask: which side am I on?

✓ 70 is in the right side of 50, so it must be larger: 70 > 50? yes

So 70 must be larger than 50. It is. 70 follows the rule.

Walk up from 80 to the root. At each ancestor (teal), ask: which side am I on?

✓ 80 is in the right side of 70, so it must be larger: 80 > 70? yes
✓ 80 is in the right side of 50, so it must be larger: 80 > 50? yes

So 80 must be larger than 70. It is. 80 follows the rule.

Tree B looks almost the same, but one node breaks the rule. Can you find it? Tap nodes to check them.

Walk up from 20 to the root. At each ancestor (teal), ask: which side am I on?

✓ 20 is in the left side of 30, so it must be smaller: 20 < 30? yes
✓ 20 is in the left side of 50, so it must be smaller: 20 < 50? yes

So 20 must be smaller than 30. It is. 20 follows the rule.

Walk up from 30 to the root. At each ancestor (teal), ask: which side am I on?

✓ 30 is in the left side of 50, so it must be smaller: 30 < 50? yes

So 30 must be smaller than 50. It is. 30 follows the rule.

Walk up from 40 to the root. At each ancestor (teal), ask: which side am I on?

✓ 40 is in the right side of 30, so it must be larger: 40 > 30? yes
✓ 40 is in the left side of 50, so it must be smaller: 40 < 50? yes

So 40 must be between 30 and 50. It is. 40 follows the rule.

Walk up from 45 to the root. At each ancestor (teal), ask: which side am I on?

✓ 45 is in the left side of 70, so it must be smaller: 45 < 70? yes
✗ 45 is in the right side of 50, so it must be larger: 45 > 50? NO

So 45 must be between 50 and 70, but it is not. This tree is not a valid BST.

50 is the root: it has no ancestors to check.

Walk up from 70 to the root. At each ancestor (teal), ask: which side am I on?

✓ 70 is in the right side of 50, so it must be larger: 70 > 50? yes

So 70 must be larger than 50. It is. 70 follows the rule.

Walk up from 80 to the root. At each ancestor (teal), ask: which side am I on?

✓ 80 is in the right side of 70, so it must be larger: 80 > 70? yes
✓ 80 is in the right side of 50, so it must be larger: 80 > 50? yes

So 80 must be larger than 70. It is. 80 follows the rule.

Your turn: valid BST or not?

Tree A

Answer

Valid. Every node passes the check.

Tree B

Answer

Not valid. 60 > 50, but it is on the LEFT.

Tree C

Answer

Not valid. 55 is in 50's LEFT subtree, so it must be less than 50. Checking only its parent (30) is not enough.

Why it matters

In Tree C, search for 55: 55 > 50 → go right to 70; 55 < 70 → go left: null. Not found, even though 55 is in the tree! One misplaced node sends the search the wrong way.

Why no duplicates?

The rule only has room for smaller (left) or larger (right). An equal value fits neither. Many uses also need unique values: one student ID = one student. (Some BSTs do allow duplicates by picking a side or counting copies.)

Part 2 · Searching

Search by hand

Search answers one question: Is this value in the tree? If yes, which node has it? Think of a registrar program finding a student's record by ID number:

The user only sees the search box. Behind it, the program walks down the tree: 2025230 is larger than 2025150, so go right. Found in 2 checks.

Search checklist

Start with current = the root. Compare the target with the current node's value:

null? → not found. Stop.
equal? → found! Stop.
smaller? → go left. Back to 1.
larger? → go right. Back to 1.

Search lab

Pick an example, or type any number and tap Search. Watch which nodes you visit.

Try an example

Color key

current visited found

Why this is fast

Searching for something larger than 50? After checking the root, the whole left subtree is skipped. Compare finding 80 in each:

Linked list: 7 checks

A list can only walk forward, one node at a time.

BST: 3 checks

80 > 50: skip the whole left side (faded). 80 > 70: skip 60. Found.

A linked list of these 7 values may need all 7 nodes checked. This BST needs at most 3.

BSTs can store names too

Names compare alphabetically: earlier in the alphabet → left, later → right. A phone's contact list or a dictionary app can search names the same way.

Part 3 · In code

BST search in Java

Each step of the checklist becomes one line of Java. We use the TreeNode class from the Trees lesson : current.data is the value, current.left and current.right are the children.

Checklist step	Java
Start at the root	`TreeNode current = root;`
1 null? → stop	`while (current != null) { ... }`
2 equal? → found	`if (target == current.data) return true;`
3 smaller? → go left	`current = current.left;`
4 larger? → go right	`current = current.right;`
Loop ended: not found	`return false;`

Now the real method. Step through search(root, 60) on the lesson tree, one check at a time:

search(root, 60), step by step

Tap any line to see what it does, or use Next to go through the code in order.

target = 60

We call search(root, 60). The method gets the tree (through root) and the value to look for: 60.

Step 1 of 13

 1static boolean search(TreeNode root, int target) { 2  TreeNode current = root; 3  while (current != null) { 4    if (target == current.data) { 5      return true; 6    } else if (target < current.data) { 7      current = current.left; 8    } else { 9      current = current.right;10    }11  }12  return false;13}

Why a while loop?

Like walking a linked list with current = current.next, but here we choose left or right at each step. The loop ends in one of two ways: return true; (found), or current becomes null and we return false;.

Your turn: trace `search(root, 45)`

No walkthrough this time. On paper, write one row each time the loop checks current: its data, and the answers to null? equal? smaller? Then check.

Show the trace table

data	null?	equal?	smaller?	Then
50	no	no	yes	go left
30	no	no	no	go right
40	no	no	no	go right
—	yes	—	—	return false

Three common mistakes

if (target = current.data): one = stores a value. Java will not compile it. Use ==.
Forgetting the line that moves current: the loop keeps checking the same node forever.
Wrong direction: smaller values are on the left.

Part 4 · Your turn

Practice

Problems 1 and 2 are on paper. The coding task at the end runs in Java.

Problem 1: trace it

For each call, write every value of current.data, in order, and what the method returns: search(root, 25) and search(root, 70).

Show the answer

Call	current.data	Result
`search(root, 25)`	40, 20, 30	false
`search(root, 70)`	40, 60, 70	true

For 25: 25 < 30, so current = current.left. 30 has no left child, so current becomes null and the loop stops.

Problem 2: find the 2 bugs

 1static boolean search(TreeNode root, int target) {
 2  TreeNode current = root;
 3  while (current != null) {
 4    if (target == current.data) {
 5      return true;
 6    } else if (target < current.data) {
 7      current = current.right;
 8    } else {
 9      current = current.left;
10    }
11  }
12  return true;
13}

Show the answer

 1static boolean search(TreeNode root, int target) {
 2  TreeNode current = root;
 3  while (current != null) {
 4    if (target == current.data) {
 5      return true;
 6    } else if (target < current.data) {
 7      current = current.right;✓current = current.left;
 8    } else {
 9      current = current.left;✓current = current.right;
10    }
11  }
12  return true;✓return false;
13}

Left and right are swapped (lines 7 and 9): smaller should go to current.left, larger to current.right.
Wrong last line (line 12): it should be return false;. With this bug, the method says every value is in the tree.

Your coding task: show the search path

When you searched by hand, you wrote down every node you checked. That list is the search path. Now let Java write it. searchPath works like the search method , but it does not just answer true or false. It gives back the path as text, for example "40 20 30 found".

Finish searchPath in about 9 lines where it says YOUR CODE. Insertion comes in the next lesson, so main links the seven nodes by hand. Run it: each printed line must match its comment.

 1public class Main {
 2  // Returns the values that a search for target visits, in order,
 3  // then "found" or "not found". Example: "40 20 30 found".
 4  static String searchPath(TreeNode root, int target) {
 5    String path = "";
 6    TreeNode current = root;
 7    // YOUR CODE (a while loop, like search):
 8    // 1. While current is not null: add current.data
 9    //    and a space to the end of path.
10    // 2. If target equals current.data, return path + "found".
11    // 3. Otherwise move current left or right, as search does.
12
13    return path + "not found";
14  }
15
16  public static void main(String[] args) {
17    // The starting BST, linked by hand: 40; 20 and 60; 10, 30, 50, 70
18    TreeNode root = new TreeNode(40);
19    root.left = new TreeNode(20);
20    root.right = new TreeNode(60);
21    root.left.left = new TreeNode(10);
22    root.left.right = new TreeNode(30);
23    root.right.left = new TreeNode(50);
24    root.right.right = new TreeNode(70);
25
26    System.out.println(searchPath(root, 30));  // expected: 40 20 30 found
27    System.out.println(searchPath(root, 55));  // expected: 40 60 50 not found
28    System.out.println(searchPath(root, 40));  // expected: 40 found
29    System.out.println(searchPath(root, 5));   // expected: 40 20 10 not found
30    System.out.println(searchPath(null, 7));   // expected: not found
31  }
32}
33
34class TreeNode {
35  int data;
36  TreeNode left;
37  TreeNode right;
38
39  TreeNode(int value) {
40    data = value;
41    left = null;
42    right = null;
43  }
44}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

Show one possible answer

 1static String searchPath(TreeNode root, int target) {
 2  String path = "";
 3  TreeNode current = root;
 4  while (current != null) {
 5    path = path + current.data + " ";
 6    if (target == current.data) {
 7      return path + "found";
 8    } else if (target < current.data) {
 9      current = current.left;
10    } else {
11      current = current.right;
12    }
13  }
14
15  return path + "not found";
16}

Output, one per line: 40 20 30 found, 40 60 50 not found, 40 found, 40 20 10 not found, not found.

It is the search loop with one new line at the top: path = path + current.data + " ";. It runs once for every node the loop checks, so the path grows one value at a time, in the same order you write them on paper. It comes before the if, so the node where the value is found is in the path too. path + current.data joins text and a number, as toBinary did in the Stacks lesson.

For 55: 55 > 40, go right. 55 < 60, go left. 55 > 50, go right, but 50 has no right child. current becomes null, the loop stops, and the last line adds not found. With an empty tree (null), the loop never runs, so the answer is just not found.

Part 5 · Check yourself

Self-check

Not graded. Tap an answer to see if you got it, and read why.

What is the BST rule?
In a BST whose root is 50, can the value 55 be anywhere in 50's left subtree?
In the lesson tree, which nodes do you visit when searching for 65?
A search reaches null. What does that mean?
Which line moves the search one level down to the left?
Why does a BST usually not store duplicate values?

Score: 0 / 6

Key takeaways

BST rule: left subtree smaller, right subtree larger, at every node.
Check a node against all its ancestors, not just its parent.
Search: compare, go left or right, stop at the value (found) or at null (not found).
In Java: start with current = root, loop while current != null.

Next lesson: BST insertion.

References

Programiz, "Binary Search Tree (BST)." programiz.com/dsa/binary-search-tree
Oracle, "The while and do-while Statements," The Java Tutorials.
N. Dale, D. T. Joyce, and C. Weems, Object-Oriented Data Structures Using Java, 4th ed. Jones & Bartlett Learning, 2018.

Keeping values in order

How to check one node

Your turn: valid BST or not?

Search by hand

Why this is fast

BST search in Java

Your turn: trace search(root, 45)

Practice

Self-check

Your turn: trace `search(root, 45)`