---

Introduction

In this blog, we will be looking into a data structure called Trees. A tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes.

The topmost node of the tree is called the root, and the nodes below it are called the child nodes. Each node can have multiple child nodes, and these child nodes can also have their own child nodes, forming a recursive structure.

Binary Search Tree

Binary Search Tree is a node-based binary tree data structure that has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.

• The right subtree of a node contains only nodes with keys greater than the node’s key.

• The left and right subtree each must also be a binary search tree.

Binary Search Tree Class

Let's look at the implementation of the Binary Tree Class:

// Node Class for Binary Search Tree

public class Node<Integer> {
    // Initialization of variables
    private Integer element;
    private Node<Integer> left;
    private Node<Integer> right;

    public Integer getElement() {
        return element;
    }

    public void setElement(Integer element) {
        this.element = element;
    }

    public Node<Integer> getLeft() {
        return left;
    }

    public void setLeft(Node<Integer> left) {
        this.left = left;
    }

    public Node<Integer> getRight() {
        return right;
    }

    public void setRight(Node<Integer> right) {
        this.right = right;
    }

    public Node(Integer element) {
        super();
        this.element = element;
        this.left = null;
        this.right = null;
    }
}

// Binary Search Tree Class
public class BinarySeacrhTree <Integer> {
    private Node<Integer> root;

    public Node<Integer> getRoot() {
        return root;
    }

    public void setRoot(Node<Integer> root) {
        this.root = root;
    }

The Binary Search Tree consists of a root Node which is further connected to other Nodes, just like a Linked List's head. This root Node can refer to other Nodes in the Binary Search Tree.

With the implementation of the Binary Search Tree done, let's dive into some of the primary and essential methods of the Binary Search Tree.

Insert into Binary Search Tree

Insertion in a Binary search tree is a slightly tricky one. However, once you wrap your mind around it, it is surprisingly easy.

Let's start with various cases of insertion:

1. The Binary Search Tree is empty:

   When the Binary Search tree is empty, the only position open for insertion is the root. So we simply set root to newNode. Let's look at the code for a better understanding

    public boolean insert(Integer element) {
            Node<Integer> newNode = new Node<>(element);
   
            if (root == null) {
                root = newNode;
                return true;
            }
        return false;
    }
   

2. The Binary Search Tree is filled:

   When the Binary Search tree is filled, we will have to check if the element we are passing is smaller or greater than the element of reference (in our case, we will be using temp to iterate over the Binary Search Tree).

   If the element stored in the temp Node is smaller than the element we have passed as an argument, we will iterate over to the left side of the Binary Search Tree.

   If the element stored in the temp Node is larger than the element we have passed as an argument, we will iterate over to the right side of the Binary Search Tree.
   We will perform the above steps until over temp Node points to a null position. When it finally reaches a terminal Node (i.e., temp points to null), we will use the setter method to set the newNode on either the left or the right side of the temp Node based on the element stored in the temp Node.
   Let's have a look at the code:

    public boolean insert(Integer element) {
            Node<Integer> newNode = new Node<>(element);
   
            if (root == null) {
                root = newNode;
                return true;
            }
   
            Node<Integer> temp = root;
   
            while (temp != null) {
                if (temp.getElement().equals(temp)) {
                    return false;
                }
                if ((int) temp.getElement() > (int) element) {
                    if (temp.getLeft() == null) {
                        temp.setLeft(newNode);
                        return true;
                    }
                    temp = temp.getLeft();
                }
                if ((int) temp.getElement() < (int) element) {
                    if (temp.getRight() == null) {
                        temp.setRight(newNode);
                        return true;
                    }
                    temp = temp.getRight();
                }
            }
            return false;
        }
   

   ---

Display Binary Search Tree

PreOrder

• For Preorder, you traverse from the root to the left subtree and then to the right subtree.

• Preorder => Parent, Left, Right.

Let's look at the Implementation of PreOrder traversal without recursion.

public void preOrder() {
        Node<Integer> temp = root;
        Stack<Node> stack = new Stack<>();

        System.out.print("PreOrder: ");
        while(temp != null || !stack.empty()) {
            while(temp != null) {
                System.out.print(temp.getElement() + " ");
                stack.push(temp);
                temp = temp.getLeft();
            }

            temp = stack.pop().getRight();
        }

        System.out.println();
    }

Let us understand the flow of code:

• We first declared a temporary node to traverse through the binary search tree. This temporary node or rather temp, is first referring to the root of our binary search tree

• In PreOrder, we first traverse to the left-most node in the binary search tree while printing its value simultaneously, then we visit the parent's right node. So using the while loop we will set temp -> temp.getLeft() until temp points to null. This will give us the leftmost node. But now the problem is we have lost the reference to the leftmost node as our temp is now pointing to null.

• To preserve the references to the nodes we have traversed through, we will be storing them in a Stack. The reason to use Stack here is, Stack follows the First-In-Last-Out approach, so when we pop the nodes we will be storing in our stack, we will get the reference to the last traversed node.

• So, as we traverse through the nodes using the while loop, we will print the element stored in the node, then store the reference of our node in our stack and then assign temp -> temp.getLeft().

• Now let's consider we have reached the leftmost node, popped the last traversed node into temp, and then set temp -> temp.getRight() and re-iterate through the steps.

Fun fact: To check if our PreOrder is working fine or not, check if the first node printed by our PreOrder is the root node or not, if it is the Root node and the number of elements in the binary search tree is equal to the number of elements printed by our PreOrder, then we can rest assured that our PreOrder is working just fine.

---

InOrder

• For Inorder, you traverse from the left subtree to the root and then to the right subtree.

• Inorder => Left, Parent, Right.

Let's look at the Implementation of InOrder traversal without recursion.

public void inOrder() {
        Node<Integer> temp = root;
        Stack<Node> stack = new Stack<>();

        System.out.print("InOrder: ");
        while(temp != null || !stack.empty()) {
            while(temp != null) {
                stack.push(temp);
                temp = temp.getLeft();
            }
            temp = stack.pop();
            System.out.print(temp.getElement() + " ");
            temp = temp.getRight();
        }
        System.out.println();
    }

Let us understand the flow of code:

• We first declared a temporary node to traverse through the binary search tree. This temporary node or rather temp, is first referring to the root of our binary search tree

• In InOrder, we first traverse to the leftmost node in the binary search tree, then we visit the parent node and then and only then we visit the parent's right node. So using the while loop we will set temp -> temp.getLeft() until temp points to null. This will give us the leftmost node. But now the problem is we have lost the reference to the left-most node as our temp is now pointing to null.

• To preserve the references to the nodes we have traversed through, we will be storing them in a Stack. When we pop the nodes we will be storing in our stack, we will get the reference to the last traversed node.

• So, as we traverse through the nodes using the while loop, we store the reference of our node in our stack and then assign temp -> temp.getLeft().

• Now let's consider we have reached the leftmost node, popped the last traversed node into temp, print the element stored in the node, and then set temp -> temp.getRight() and re-iterate through the steps.

Fun fact: To check if our InOrder is working or not, we just need to check if our InOrder has printed all the elements of our binary search tree in ascending order. If it did so, then rest assured, our InOrder is working just fine.

---

PostOrder

• For Post order, you traverse from the left subtree to the right subtree and then to the root.

• Post order => Left, Right, Parent.

Let's look at the Implementation of PostOrder traversal without recursion.

public void postOrder() {
        class Pair {
            Node<Integer> node;
            char flag;

            public Pair(Node<Integer> node, char flag) {
                this.node = node;
                this.flag = flag;
            }
        }

        Node<Integer> temp =root;
        Stack<Pair> stack = new Stack<>();
        System.out.print("PostOrder: ");
        while(temp != null || !stack.empty()) {
            while(temp != null) {
                stack.push(new Pair(temp, 'L'));
                temp = temp.getLeft();
            }

            Pair pair = stack.pop();
            if(pair.flag == 'L') {
                temp = pair.node.getRight();
                pair.flag = 'R';
                stack.push(pair);
            }
            else {
                System.out.print(pair.node.getElement() + " ");
            }
        }
        System.out.println();
    }

Let us understand the flow of code:

• We first declared a temporary node to traverse through the binary search tree. This temporary node or rather temp, is first referring to the root of our binary search tree

• In PostOrder, we first traverse to the left-most node in the binary search tree, then we visit the parent's right node and then visit the parent Node. So using the while loop we will set temp -> temp.getLeft() until temp points to null. This will give us the leftmost node. But now the problem is we have lost the reference to the leftmost node as our temp is now pointing to null.

• To preserve the references to the nodes we have traversed through, we will be storing them in a Stack. The reason to use Stack here is, Stack follows the First-In-Last-Out approach, so when we pop the nodes we will be storing in our stack, we will get the reference to the last traversed node.

• One major problem we will face in the case of PostOrder is that when we pop back the parent node, the system would not be able to understand if it had to iterate to the left or the right side of the binary search tree. So to be able to decide which side

• So, as we traverse through the nodes using the while loop, we will print the element stored in the node, then store the reference of our node in our stack and then assign temp -> temp.getNext().

• Now let's consider we have reached the leftmost node, popped the last traversed node into temp, and then set temp -> temp.getRight() and re-iterate through the steps.

Fun fact: To check if our PostOrder is working fine or not, check if the last node printed by our PostOrder is the root node or not. If it is the Root node and the number of elements in the binary search tree is equal to the number of elements printed by our PostOrder, then we can rest assured that our PostOrder is working just fine.

---

Using Recursion

As easy as it might be to understand the display methods of Binary Search Tree, the above methods could seem a little daunting. However, using Recursion, we can cut down the implementation to just a few lines of code. Let's look at the code first and then we will try to understand how it works.

public void printInOrder(Node<Integer> node) {
        // Left-Parent-Right

        if (node == null)
            return;

        printInOrder(node.getLeft());
        System.out.print(node.getElement() + " ");
        printInOrder(node.getRight());
    }

public void printPreOrder(Node<Integer> node) {
        // Parent-Left-Right

        if (node == null)
            return;

        System.out.print(node.getElement() + " ");
        printPreOrder(node.getLeft());
        printPreOrder(node.getRight());
    }

public void printPostOrder(Node<Integer> node) {
        // Left-Right-Parent

        if (node == null)
            return;

        printPostOrder(node.getLeft());
        printPostOrder(node.getRight());
        System.out.print(node.getElement() + " ");
    }

Let's first look at the printPreOrder(). The steps we follow for printing elements using the preOrder method are: Left --> Root --> Right.

So we will recursively call the printPreOrder method on node.getLeft(), then print(root) and then recursively call node.getRight().

Our return condition here would be that our traversing node starts pointing to null.

Similarly, in the case of printInOrder(), we follow: Root --> Left --> Right.
So the methods to be called are:
print(root);
node.getLeft();
node.getRight();

And lastly, in the case of printPostOrder(), we follow: Left --> Right --> Root
So the methods to be called are:
node.getLeft();
node.getRight();
print(root);

With this, we have successfully implemented all three traversal methods used to traverse through a Binary Search Tree.

In the next part of this Blog, we will look into the delete() of the binary search tree, along with some other functional methods like getMin(), getMax() and so on.

I hope this helps!! I strongly recommend you to go over to Kunal Kushwaha's Complete DSA Playlist. It will definitely help you understand the concepts better. Or you can refer to this video on the binary search tree.

Once again, Thank you for reading this article.

Happy Learning!!