Java binary search trees

Before you start

Java recursion and classes.

Insert values into a tree that keeps smaller values on the left, and traverse it in sorted order.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

A binary search tree (BST) stores values so that, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. Searching and inserting follow one path from the root, comparing at each step, so they take time proportional to the height of the tree.

An in-order traversal visits the left subtree, then the node, then the right subtree, and so it produces the values in sorted order. A balanced tree with n nodes has height about log2(n), but inserting sorted data into a plain BST creates a long chain of height n. Self-balancing trees such as red–black trees (used by TreeMap) prevent this.

Code example

Java

import java.util.*;

class Main {
  static class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
      this.value = value;
    }
  }

  static Node insert(Node root, int value) {
    if (root == null) {
      return new Node(value);
    }
    if (value < root.value) {
      root.left = insert(root.left, value);
    } else if (value > root.value) {
      root.right = insert(root.right, value);
    }
    return root;
  }

  static boolean contains(Node root, int value) {
    while (root != null) {
      if (value == root.value) {
        return true;
      }
      root = value < root.value ? root.left : root.right;
    }
    return false;
  }

  static void inOrder(Node root, List<Integer> out) {
    if (root == null) {
      return;
    }
    inOrder(root.left, out);
    out.add(root.value);
    inOrder(root.right, out);
  }

  static int height(Node root) {
    return root == null ? 0 : 1 + Math.max(height(root.left), height(root.right));
  }

  public static void main(String[] args) {
    Node root = null;
    for (int v : new int[] {50, 30, 70, 20, 40, 60, 80, 40}) {
      root = insert(root, v);
    }
    List<Integer> sorted = new ArrayList<>();
    inOrder(root, sorted);
    System.out.println(sorted);
    System.out.println(contains(root, 60) + " " + contains(root, 65));
    System.out.println("height " + height(root));

    Node chain = null;
    for (int v = 1; v <= 7; v++) {
      chain = insert(chain, v);
    }
    System.out.println("height of the chain " + height(chain));
  }
}

Output

[20, 30, 40, 50, 60, 70, 80]
true false
height 3
height of the chain 7

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1import java.util.*;

3class Main {

4 static class Node {

5 int value;

6 Node left;

7 Node right;

9 Node(int value) {

10 this.value = value;

11 }

12 }

14 static Node insert(Node root, int value) {

15 if (root == null) {

16 return new Node(value);

17 }

18 if (value < root.value) {

19 root.left = insert(root.left, value);

20 } else if (value > root.value) {

21 root.right = insert(root.right, value);

22 }

23 return root;

24 }

26 static boolean contains(Node root, int value) {

27 while (root != null) {

28 if (value == root.value) {

29 return true;

30 }

31 root = value < root.value ? root.left : root.right;

32 }

33 return false;

34 }

36 static void inOrder(Node root, List<Integer> out) {

37 if (root == null) {

38 return;

39 }

40 inOrder(root.left, out);

41 out.add(root.value);

42 inOrder(root.right, out);

43 }

45 static int height(Node root) {

46 return root == null ? 0 : 1 + Math.max(height(root.left), height(root.right));

47 }

49 public static void main(String[] args) {

50 Node root = null;

51 for (int v : new int[] {50, 30, 70, 20, 40, 60, 80, 40}) {

52 root = insert(root, v);

53 }

54 List<Integer> sorted = new ArrayList<>();

55 inOrder(root, sorted);

56 System.out.println(sorted);

57 System.out.println(contains(root, 60) + " " + contains(root, 65));

58 System.out.println("height " + height(root));

60 Node chain = null;

61 for (int v = 1; v <= 7; v++) {

62 chain = insert(chain, v);

63 }

64 System.out.println("height of the chain " + height(chain));

65 }

66}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Smaller values go into the left subtree, larger values into the right. Duplicates, like the second 40, are ignored.	`—`	—
Search follows one path, discarding half of the remaining tree if it is balanced.	`—`	—
In-order: the node is visited between its left and right subtrees.	`—`	—
The traversal returns the values in sorted order.	`—`	[20, 30, 40, 50, 60, 70, 80]
60 is in the tree and 65 is not.	`—`	[20, 30, 40, 50, 60, 70, 80] true false
Seven values fit in a perfectly balanced tree of height 3.	`—`	[20, 30, 40, 50, 60, 70, 80] true false height 3
Inserting 1 to 7 in order builds a chain of height 7, so a search takes O(n).	`—`	[20, 30, 40, 50, 60, 70, 80] true false height 3 height of the chain 7

Behind the scenes

How Java processes this code

The Java compiler produces bytecode. The JVM loads the class and invokes its main method.

Cost and common mistakes

Search and insert O(h), where h is the height: O(log n) if balanced, O(n) in the worst case.

A plain BST has no balance guarantee. Sorted input gives worst-case O(n) operations.
Deep recursion can overflow the stack on a very tall tree. An iterative version avoids that.
Deleting a node with two children needs care: replace it by its in-order successor.

Try it yourself

In which order does a pre-order traversal visit the first tree?

Reveal answer and reasoning

50, 30, 20, 40, 70, 60, 80: the node first, then the left subtree, then the right subtree.