Java Binary Search Tree Traversal

Copy Link LinkedIn Message Facebook Email X

This lesson details the code required to traverse a binary search tree.

How to Traverse a Binary Search Tree

This is the only way to gain access to the data stored in the tree! At times, it is useful to traverse an entire tree, for instance, if you want to print out or evaluate every element in the tree.

Just like any other data structure, it can be useful to be able to iterate over the entire data set therein. But how do you iterate over a tree? Great question!

There are three common methods for iterating over a tree:

1. In-Order Traversal (left -> root -> right)
   • Given the tree above, it would print: 3, 5, 6, 8, 9, 10, 12, 16
2. Pre-Order Traversal (root -> left -> right)
   • Given the tree above, it would print: 10, 5, 3, 8, 6, 9, 12, 16
3. Post-Order Traverse (left -> right -> root)
   • Given the tree above, it would print: 3, 6, 9, 8, 5, 16, 12, 10

Take a look at how each of these work.

In-Order Traversal

When traversing a binary search tree in-order, it would follow a path like the one in this gif:

Issac Chua, CC BY-SA 4.0, via Wikimedia Commons

Traversal Algorithm

1. Check if the current node is empty or null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

Example

In a binary search tree, in-order traversal retrieves data in sorted order.

/**
   * Prints the data of each Node using pre-order traversal recursively
   * @param node the starting Node
*/
public void printInorderRecursive(Node node) {
  if (node == null)
    return;
  // first, recursively traverse all the way down the left side of the tree
  printInorderRecursive(node.leftChild);
  // then print out the data at each node
  System.out.print(node.data + " ");
  // then, recurse down the right side (of each subtree)
  printInorderRecursive(node.rightChild);
}

Pre-Order Traversal

When traversing a binary search tree pre-order, it would follow a path like the one in this gif:

Issac Chua, CC BY-SA 4.0, via Wikimedia Commons

Traversal Algorithm

1. Check if the current node is empty or null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function.

Example

In a binary search tree, pre-order traversal retrieves data in descending order while prioritizing the left children.

/**
   * Prints the data of each Node using pre-order traversal recursively
   * @param node the starting Node
*/
public void printPreorderRecursive(Node node) {
  if (node == null) return;
  // print out the data first
  System.out.print(node.data + " ");
  // recurse down the left tree
  printPreorderRecursive(node.leftChild);
  // recurse down the right tree
  printPreorderRecursive(node.rightChild);
}

Post-Order Traversal

When traversing a binary search tree post-order, it would follow a path like the one in this gif: Issac Chua, CC BY-SA 4.0, via Wikimedia Commons

Traversal Algorithm

1. Check if the current node is empty or null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

Example

In a binary search tree, pre-order traversal retrieves data while prioritizing the leaves of the tree.

/**
   * Prints the data of each Node using 
   * post-order (aka "bottoms up") traversal recursively
   * @param node the starting Node
*/
public void printPostorderRecursive(Node node) {
  if (node == null)
    return;
  // first recur down the left subtree
  printPostorderRecursive(node.leftChild);
  // then recur down then right subtree
  printPostorderRecursive(node.rightChild);
  // now print the data at each node
  System.out.print(node.data + " ");
}

Summary: Java Binary Search Tree Traversal

• Traversing a binary search tree allows you to access the elements inside the tree
• There are three ways to traverse a binary search tree: in-order, pre-order and post-order

In-Order Traversal Algorithm

1. Check if the current node is empty or null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

Pre-OrderTraversal Algorithm

1. Check if the current node is empty or null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function.

Post-Order Traversal Algorithm

1. Check if the current node is empty or null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).