BST Insertion

Problem 1: trace table

Using the starting BST (40, 20, 60, 10, 30, 50, 70), make a trace table for insert(root, 55): one row each time the loop checks a node.

Problem 2: build and answer

Start with an empty tree. Insert, in this order: 50, 30, 75, 25, 40, 35, 90, 80, 95

Draw it on paper first. Then build it below, placing the values in the same order, and tap Check.

1. Draw the final BST.
2. Which node is the parent of 35?
3. If we then call insert(root, 85), which nodes does current visit? Where is 85 connected?
4. What happens if we call insert(root, 40)?

Problem 3: find the bug

A classmate inserted 45, but 45 never appears in the tree. Which line is wrong?

 1} else if (value < current.data) {
 2  if (current.left == null) {
 3    current = new TreeNode(value);
 4    return root;
 5  }
 6  current = current.left;
 7}

Your coding task: insert with a parent pointer

Our insert looks before each move: is the spot on that side empty? Many books write insert another way. They walk down until current falls off the tree (becomes null), and they keep a second variable, parent, one step behind it. When current is null, parent is the node that gets the new child.

Why a second variable? Remember Mistake 2 : current = new TreeNode(…) only moves the arrow. Once current is null, it cannot connect anything. parent still refers to a real node, so parent.left = newNode; really connects the new node.

Finish insert where it says YOUR CODE: about 15 short lines, and many of them are just braces. main builds the starting BST with the same for loop as before, then inserts 55, 25, and 30 again. Run it: each printed line must match its comment.

 1public class Main {
 2  // Inserts value into the BST and returns the root.
 3  // Duplicates are skipped.
 4  static TreeNode insert(TreeNode root, int value) {
 5    TreeNode newNode = new TreeNode(value);
 6    if (root == null) {
 7      return newNode;
 8    }
 9    TreeNode parent = null;
10    TreeNode current = root;
11    // YOUR CODE:
12    // 1. Walk down. While current is not null:
13    //    - if value equals current.data, return root (skip it);
14    //    - set parent = current, then move current
15    //      left or right.
16    // 2. Now current is null, and parent is the last node
17    //    visited. Connect newNode as parent's left child
18    //    if value < parent.data, otherwise as its right child.
19
20    return root;
21  }
22
23  public static void main(String[] args) {
24    int[] values = {40, 20, 60, 10, 30, 50, 70};
25    TreeNode root = null;
26    for (int i = 0; i < values.length; i++) {
27      root = insert(root, values[i]);
28    }
29    System.out.println(root.data);                   // expected: 40
30    System.out.println(root.right.left.data);        // expected: 50
31
32    root = insert(root, 55);
33    System.out.println(root.right.left.right.data);  // expected: 55
34    root = insert(root, 25);
35    System.out.println(root.left.right.left.data);   // expected: 25
36    root = insert(root, 30);                         // a duplicate
37    System.out.println(root.left.right.right == null); // expected: true
38  }
39}
40
41class TreeNode {
42  int data;
43  TreeNode left;
44  TreeNode right;
45
46  TreeNode(int value) {
47    data = value;
48    left = null;
49    right = null;
50  }
51}

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

Before you write the loop, the starter prints 40 and then stops with a NullPointerException: only the first value (40) was kept, so root.right is null. That is expected.

 1static TreeNode insert(TreeNode root, int value) {
 2  TreeNode newNode = new TreeNode(value);
 3  if (root == null) {
 4    return newNode;
 5  }
 6  TreeNode parent = null;
 7  TreeNode current = root;
 8  while (current != null) {
 9    if (value == current.data) {
10      return root;
11    }
12    parent = current;
13    if (value < current.data) {
14      current = current.left;
15    } else {
16      current = current.right;
17    }
18  }
19  if (value < parent.data) {
20    parent.left = newNode;
21  } else {
22    parent.right = newNode;
23  }
24
25  return root;
26}