CodeNewbie Community 🌱

Cover image for Traversing a Binary Search Tree in Java
Tristan
Tristan

Posted on

Traversing a Binary Search Tree in Java

Introduction

  • Lets do some computer science in Java!!

Video version

GitHub code

What we are doing

  • Before you dive into this, you should have a basic understanding on how recursion works
  • Today we are going to talk about Binary Search Trees and how to traverse them. We are going to be looking at depth first traversal and the breadth first traversal. But before we go any further lets talk a little about trees in general

Trees

  • A quick run down on trees is that they are a non-linear data structure made up of nodes(we will elaborate on nodes when we start building a tree) that must abide by these three general rules:

1) Each tree has a root node

2) The root node has zero or more children

3) Each child node has zero or more child nodes and so one

  • Now there are several different types of trees but we we are specifically interested in Binary Search Trees (BST).

Binary Tree

  • A Binary Tree(BT) is a tree in which each node has up to two children. Which is not the norm for all trees. In fact a Ternary Tree is a type of tree where each node has three children. So any time we see a Tree data structure that has Binary in its name, we know that each of it's nodes has at most 2 children.
  • Ok then what is the difference between a Binary Search Trees and a Binary Tree?

Binary Search Trees

  • A BST differs from a BT in the face that every individual node fits the specific ordering: left descendants <= n all right descendants for each node n. What that means is that all children left of a node will be less than it and all the children right of the node will be greater than it. A BST looks like this

Binary Search Tree

  • notice the ordering of the numbers. A BT does not have to keep that ordering.

Unbalanced vs Balanced trees

  • Now if you have read about trees at all then you have probably heard about balancing and that you should make sure your trees are balanced. Which is true, an unbalanced BST loses all of it's search efficiencies. However, to keep things simple we are not going to be talking about how to balance a tree, that will be in a later post when we talk bout AVL trees. Instead we are just going to make a simple tree that will allow us to traverse it.

Binary Search Tree implementation

  • Creating and implementing our simple BST can be broken down into 4 steps

1) create the node
2) create insert method
3) create depth first methods
4) create breadth first method

1) create the node

  • For the sake of simplicity and ease of use we are going to nest a Node class inside of our BST class, it will look something like this:
public class BinarySearchTree {
    private int size = 0;
    private Node root = null;


    protected class Node{
        private int element;
        private Node leftChild;
        private Node rightChild;

        public Node(int element,Node leftChild, Node rightChild){
            this.element = element;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }

        //GETTERS
        public int getElement(){
            return this.element;
        }
        public Node getLeftChild(){
            return this.leftChild;
        }
        public Node getRightChild(){
            return this.rightChild;
        }
        //SETTERS
        public void setElement(int element) {
            this.element = element;
        }
        public void setLeftChild(Node leftChild) {
            this.leftChild = leftChild;
        }
        public void setRightChild(Node rightChild) {
            this.rightChild = rightChild;
        }
    }
}

Enter fullscreen mode Exit fullscreen mode
  • As you can see the Node class is really just a basic POJO and all it holds is an element and a reference to two child nodes.

  • You will also notice that we are also keeping track of the first node inserted(the root) and giving it an initial value of null, private Node root = null. This is crucial because it will be used by our methods to determine if there are any nodes to traverse

2) create insert method

  • This insert method is not going to be too complicated, but just remember that when inserting a Node it must abide by this ordering specification: left decendants <= n < right decendants for each node n. Now we are also going to break this insert method up into two different methods. With that being said lets create the first method:
   public void insert(int item){
        Node newNode = new Node(item,null,null);
        if(root == null){
            root = newNode;
        }else{
            insertNode(this.root,newNode);
        }
        this.size ++;
    }

Enter fullscreen mode Exit fullscreen mode
  • If the root is null, that means the tree is empty and we add a new node as the root. If the root is not null we call the insertNode(this.root,newNode) with the root and the newNode. The insertNode method is where the majority of the work is going on. So the method looks like this:
private void insertNode(Node node,Node newNode){
        if(newNode.element < node.element){
            if (node.getLeftChild() == null){
                node.setLeftChild(newNode);
            }else{
                insertNode(node.getLeftChild(),newNode);
            }
        }else{
            if(node.getRightChild() == null){
                node.setRightChild(newNode);
            }else{
                insertNode(node.getRightChild(),newNode);
            }
        }
    }

Enter fullscreen mode Exit fullscreen mode
  • The first conditional, newNode.element < node.element is used to check which side of the current node our new node belongs on. If the conditional is true, that means it belongs on the left side, if it is false, it belongs on the right side. This conditional also acts as our base case for the recursion:
if (node.getLeftChild() == null){
                node.setLeftChild(newNode);
            }else{
                insertNode(node.getLeftChild(),newNode);
            }
}

Enter fullscreen mode Exit fullscreen mode
  • This conditional is used to determine if we have found the place where our node goes or if we need to keep traversing the tree. The insertNode(node.getLeftChild(),newNode) method is a recursive method call.

  • The second conditional:

else{
            if(node.getRightChild() == null){
                node.setRightChild(newNode);
            }else{
                insertNode(node.getRightChild(),newNode);
            }
        }

Enter fullscreen mode Exit fullscreen mode
  • The code above is the exact mirror of our previous code, meaning that this code is run when newNode.element < node.element

  • So now that we have our insertion method up and running, lets start traversing.

3) create depth first methods

  • Now Depth-first traversal DFT is a method for exploring a tree or graph. In a DFT, you go as deep as possible down one path before backing up and trying a different one.
  • There are 3 different approaches to a depth first traversal:

1)in-order
2)pre-order
3)post-order

in-order traversal
  • A in-order traversal visits all the nodes of a BST in ascending order. which means it visits the nodes from the smallest to the largest and its implementation looks like this:
 public void inOrderTraversal(){
        inOrderTraversalNode(this.root);
    }
    private void inOrderTraversalNode(Node node){
        if(node != null){
            inOrderTraversalNode(node.getLeftChild());
            System.out.println(node.element);
            inOrderTraversalNode(node.getRightChild());
        }
    }

Enter fullscreen mode Exit fullscreen mode
  • First I want you to notice that yet again we are breaking things up into two methods. This time it is for ease of use, so we can simply call the inOrderTraversal() method without having to pass it the root node.

  • Then if we look at the inOrderTraversalNode(Node node) method notice how we are using recursion and how weirdly simple it is.

  • You will see in the pre and post traversal methods the only difference between these methods is where we put the action or in our case the: System.out.println(node.element).

pre-order traversal
  • A pre-order traversal visits the node prior to its descendants, which sounds a little confusing but the code clears things:
    public void preOrderTraversal(){
        preOrderTraversalNode(this.root);
    }
    private void preOrderTraversalNode(Node node){
        if(node != null){
            System.out.println(node.element);
            inOrderTraversalNode(node.getLeftChild());
            inOrderTraversalNode(node.getRightChild());
        }
    }

Enter fullscreen mode Exit fullscreen mode
post-order traversal
  • Post order traversal visits the node after it visits descendants:
    public void postOrderTraversal(){
        postOrderTraversalNode(this.root);
    }
    private void postOrderTraversalNode(Node node){
        if(node != null){
            inOrderTraversalNode(node.getLeftChild());
            inOrderTraversalNode(node.getRightChild());
            System.out.println(node.element);
        }
    }
Enter fullscreen mode Exit fullscreen mode
  • These methods are nothing too complicated. However, the breadth first traversal does get a little complicated

Breadth first traversal

  • Another approach is to traverse a tree so that we visit all the positions at depth d before we visit the positions at d + 1.

  • This traversal algorithm is not recursive, since we are not traversing the entire tree at once. We will use a Queue for its first in first out order in which we visit the nodes. This method can get a little confusing so I have broken it down into 6 parts:

1) define the returned list
2) check if the root is empty
3) create internal queue and add the root
4) while loop for non empty queue
5) run the children() method
6) return the list

  • As you can see this is quite a few steps but lets get started:

1) define the returned list

public List<Node> breadthFirstSearch(){
        List<Node> breadthList = new ArrayList<>();
}

Enter fullscreen mode Exit fullscreen mode
  • We start off with defining our method, which is going to return a List. This list is going to contain all the nodes in a proper breadth first order.

2) check if the root is empty

public List<Node> breadthFirstSearch(){
        List<Node> breadthList = new ArrayList<>();
        if(this.root == null){
            return null;
        }else{
       }
}

Enter fullscreen mode Exit fullscreen mode
  • This section is just a simple conditional check to determine if the root is null. If it is null we just return null, if it is not null we enter the else conditional where we will do the actual traversal.

3) create internal queue and add the root

public List<Node> breadthFirstSearch(){
 //all previous code included
        else{
            Queue<Node> queue = new LinkedList();
            queue.add(this.root);

       }
}

Enter fullscreen mode Exit fullscreen mode
  • Since the queue is just an interface in Java we can use polymorphism and instantiate it with a LinkedList. Then we add the root to the queue.

4) while loop for non empty queue

public List<Node> breadthFirstSearch(){
 //all previous code included
        else{
            Queue<Node> queue = new LinkedList();
            queue.add(this.root);
            while(!queue.isEmpty()){
                Node node = queue.remove();
                breadthList.add(node);

       }
}

Enter fullscreen mode Exit fullscreen mode
  • Now we create a while loop that will run as long as the queue is not empty. Inside of that while loop we remove the first node inside of our queue, Node node = queue.remove(). Then we add it to the list we are going to return breadthList.add(node);.

5) run the children() method

public List<Node> breadthFirstSearch(){
 //all previous code included
        else{
            Queue<Node> queue = new LinkedList();
            queue.add(this.root);
            while(!queue.isEmpty()){
                Node node = queue.remove();
                breadthList.add(node);
                //notice the children() method
                for (Node n:children(node)){
                    queue.add(n);
                }

       }
}

Enter fullscreen mode Exit fullscreen mode
  • So look at the for loop we have created:
   for (Node n:children(node)){
              queue.add(n);
                }
Enter fullscreen mode Exit fullscreen mode
  • This loop is actually what keeps our while loop going and adding to the queue. Ok but what exactly is the children method?
 private List<Node> children(Node node){
        List<Node> list = new ArrayList<>(2);
        if(node.getLeftChild() != null){
            list.add(node.getLeftChild());
        }
        if(node.getRightChild() != null){
            list.add(node.getRightChild());
        }
        return list;
    }
Enter fullscreen mode Exit fullscreen mode
  • Its a very simple method that checks if the node it is called with has any children and if it does it returns a list with those children. Then thanks to the previously mentioned for loop, those children get added to the queue

6) return the list

  • Last thing we do is have our method return the breadthList that contains the properly ordered nodes:
    public List<Node> breadthFirstSearch(){
        List<Node> breadthList = new ArrayList<>();
        if(root == null){
            return null;
        }else{
            Queue<Node> queue = new LinkedList();
            queue.add(this.root);
            while(!queue.isEmpty()){
                Node node = queue.remove();
                breadthList.add(node);
                for (Node n:children(node)){
                    queue.add(n);
                }

            }
        }

        return breadthList;

    }


Enter fullscreen mode Exit fullscreen mode

Conclusion

  • Thank you for taking the time out of your day to read this blog post of mine. If you have any questions or concerns please comment below or reach out to me on Twitter

Oldest comments (0)