BST Insertion & In-Order Traversal: A Beginner's Guide

Introduction

In our previous exploration at Art Of Coding, we discussed the basics of tree data structures, providing a foundational understanding of this concept in computer science. Today, we take a step further into a specific type of tree: the Binary Search Tree (BST).

In this article ‘BST Insertion & In-Order Traversal: A Beginner’s Guide’ , we will specifically address how to insert data into a BST and how to print that data by employing the in-order traversal method. We will illustrate this practical implementation with Java code, offering you a step-by-step guide to not only understand but also to put these operations into practice.

By the end of this article, you’ll have a clear understanding of how to implement and work with Binary Search Trees in Java.

A Quick Review of Binary Search Trees (BST)

Before we delve into the implementation of BST operations in Java, let’s quickly review what a Binary Search Tree is and why it’s important.

What is a Binary Search Tree?

A Binary Search Tree is a special form of tree where each node has up to two children, known as the left and right child. The defining feature of a BST is that it maintains a specific order: for any given node, all the elements in its left subtree are smaller, and all the elements in its right subtree are larger. This makes BSTs highly efficient for operations like searching and sorting data.

The image below illustrates a binary search tree (BST), showcasing how each node is positioned according to BST properties.

Tree Traversal Techniques in Binary Search Trees

As we continue to explore Binary Search Trees (BSTs), it’s essential to understand different methods of traversing these trees. While there are three primary traversal techniques – pre-order, in-order, and post-order – today, we will focus specifically on in-order traversal. This decision is to keep our discussion concise and digestible, especially for beginners. We plan to cover pre-order and post-order traversals in more detail in future articles.

Why In-Order Traversal?

In-order traversal, which visits nodes in the left subtree, the root, and then the right subtree. This method results in visiting all the nodes in ascending order, which is a practical way to display the outcome of our insertion method. By implementing in-order traversal, we can effectively demonstrate how the BST organizes data, ensuring that each left node is less than its parent node, and each right node is greater.

For the Binary Search Tree (BST) shown in the image above, an in-order traversal would visit the nodes in the following order: 3, 5, 6, 10, 12, 15, 18.

BST Insertion & In-Order Traversal: Java Implementation

In this section, we will implement a BST in Java. Specifically, we’ll examine how to construct a BST, add new elements to it, and perform an in-order traversal to display the elements in a sorted manner.

Let’s dive into the code!

public class Node {
  
    int value;
    // Reference to the left child node
    Node left;
    // Reference to the right child node
    Node right;

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


    public void add(int newValue) {
        if (newValue < this.value) {
            // If newValue is less than the current node's value, go left
            if (this.left == null) {
                // If left child is null, create a new node and assign it
                this.left = new Node(newValue);
            } else {
                // If left child exists, recursively call add on the left subtree
                this.left.add(newValue);
            }
        } else {
            // If newValue is greater than or equal to the current node's value, go right
            if (this.right == null) {
                // If right child is null, create a new node and assign it
                this.right = new Node(newValue);
            } else {
                // If right child exists, recursively call add on the right subtree
                this.right.add(newValue);
            }
        }
    }

    // Method to print the BST nodes in an in-order traversal
    public void printInOrder() {
        if (this.left != null) {
            // Recursively print the left subtree first
            this.left.printInOrder();
        }
        // Print the current node's value
        System.out.println(this.value);
        
        if (this.right != null) {
            // Recursively print the right subtree
            this.right.printInOrder();
        }
    }
}

Java Implementation Explained

Value: The data value stored in the node.
Left Child: A reference to the left child node, which contains values less than the node’s value.
Right Child: A reference to the right child node, which contains values greater than the node’s value.

The `Node` Constructor

The constructor public Node(int value) sets the initial value of the node when a new node is created.

The `add` Method

The add method is used to insert a new value into the BST.
It compares the new value (newValue) with the current node’s value.
- If newValue is less than the current node’s value, it goes to the left subtree.
  - If the left child is null, a new node with newValue is created as the left child.
  - If the left child is not null, the add method is called recursively on the left child.
- If newValue is greater than or equal to the current node’s value, it follows the same logic but for the right subtree.

The `printInOrder` Method

This method prints the values of the BST in an in-order traversal (left node, root node, right node).
It first recursively prints the left subtree, then the current node’s value, and finally the right subtree.
This results in the values being printed in ascending order.

Complexity Analysis of Binary Search Tree Operations

Inserting an Element in a BST

The process of adding an element to a BST involves traversing the tree from the root to the appropriate leaf node. At each node, you make a decision: if the new element is smaller, you go left; if larger, you go right.

Best-case Scenario: The best-case time complexity for inserting an element into a BST is O(log n), where n is the number of nodes in the tree. This occurs when the BST is perfectly balanced, meaning each node has two children (except for the leaves) and the tree has the smallest possible height.

Worst-case Scenario: The worst-case time complexity is O(n), which happens when the BST is completely unbalanced — essentially becoming a linked list (e.g., when all the elements are inserted in ascending order). Example: 10 –>11 –>12–>13.

In-Order Traversal of a BST

In-order traversal is a method to visit all the nodes of a BST in ascending order. Starting from the leftmost node, you visit the left subtree, then the node itself, and finally the right subtree.

Time Complexity: The time complexity of in-order traversal is always O(n), regardless of the tree’s shape. This is because each node in the tree is visited exactly once.

Wrapping Up and Looking Ahead 🚀

We’ve thoroughly examined BST Insertion & In-Order Traversal within Binary Search Trees. These are just the first steps towards mastering BSTs and their applications.

Looking ahead, we’ll cover more BST operations such as various traversal methods and strategies for finding minimum and maximum values. Keep an eye out for these future articles to deepen your understanding of BSTs.

👀Stay tuned to Art Of Coding for more on BSTs and join the conversation by sharing your thoughts and questions.

Until next time, happy coding! 👨‍💻👩‍💻

References

Cracking the Coding Interview: This book is a renowned best-seller and a personal favorite – an essential book for preparing for technical interviews!
Designing Data-Intensive Applications: ‘ is a go-to reference for creating scalable, robust, and high-performance applications!

BST Insertion & In-Order Traversal: A Beginner’s Guide