A binary tree is a data structure in which each node can have between 1 and 2 children. Here is an example of one:

2000px-Binary_search_tree.svg

 

The 8 here is the ‘root’ of the tree, and the bottom of the tree consists of the ‘leaves’ (which have no children). In this case, we call this type of binary tree a Binary Search Tree. This is because each parent is greater than or equal to its left child, and its right child is greater than or equal to the parent. This makes traversing the tree extremely easy and also makes it’s search complexity time O(log n). We’re in essence, halving the search space with every iteration downward.

 

Each node is almost like a LinkedList, however instead of just containing one ‘next’ item, they contain two (a right and left child). Let’s get started by coding a Node for a binary tree.

 

class Node {

    // the key is used to compare nodes
    int key;
    // this is the data each node stores
    String value;

    // binary tree's have nodes that can contain
    // a left child, a right child or both
    Node leftChild;
    Node rightChild;

    // we require a key and a value to create a node
    Node(int key, String value) {

        this.key = key;
        this.value = value;

    }

    public String toString() {

        return "key: " + key + "value: " + value;

    }

}

If you’re familiar with LinkedLists from the previous sections, this should be pretty straight forward for you. Now is where things change up a bit – the BinaryTree class:

class BinarySearchTree{

    Node root;

    public void addNode(int key, String value){

        // Create a new Node and initialize it
        Node newNode = new Node(key, name);

        // If there is no root this becomes root
        if (root == null) {

            root = newNode;

        } else {

            // Set root as the Node we will start
            // with as we traverse the tree
            Node focusNode = root;

            // future parent for new Node
            Node parent;

            while(true){

                //root is the parent, so we start there
                parent = focusNode;

                //check if we should go left or right
                if(key < focusNode.key){

                    focusNode = focusNode.leftChild;

                    // if the left child has no children
                    if(focusNode == null){

                        // then place the new node on the left of it
                        parent.leftChild = newNode;
                        return;
                    }

                } else {

                    // if we get here, put it on the right
                    focusNode = focusNode.rightChild;

                    if(focusNode == null){

                        parent.rightChild = newNode;
                        return; // done

                    }

                }

            }
 
        }

    }

}

Now we have a surefire way to add nodes into the correct places of our BinarySearchTree! Pretty simple actually, if you just follow the logic through. The key is to remember the bigger goal. Now, what about traversing the tree?

Well, there’s 3 ways. Pre-order, in-order and post-order traversal. Let’s do into what each of these mean in detail.

Pre-Order Traversal

public void preorderTraverseTree(Node focusNode) {

    if (focusNode != null) {

        System.out.println(focusNode);
        preorderTraverseTree(focusNode.leftChild);
        preorderTraverseTree(focusNode.rightChild);

    }

}

Pre-order traversal goes from the root to the left side and explores that side first. Once it reaches the end of the left side, it does the same on the right.

In-order Traversal

 

public void inOrderTraverseTree(Node focusNode) {

    if (focusNode != null) {

        // Traverse the left node
        inOrderTraverseTree(focusNode.leftChild);

        // Visit the currently focused on node
        System.out.println(focusNode);

        // Traverse the right node
        inOrderTraverseTree(focusNode.rightChild);

    }

}

In-order traversal iterates through the lowest, to the highest keys. See the diagram above.

Post-order Traversal

 

public void postOrderTraverseTree(Node focusNode) {

    if (focusNode != null) {

        postOrderTraverseTree(focusNode.leftChild);
        postOrderTraverseTree(focusNode.rightChild);

        System.out.println(focusNode);

    }

}

Post-order traversal explores the left side starting with the leaves first and works its way up to the root. After it hits the root node, it does the same thing on the right side.

Now let’s put all of our knowledge to work with a practice question from ‘Cracking the Coding Interview’.

 

Implement a function to check if a binary tree is a binary search tree.

This question is easy. All we have to do is iterate down the tree in pre-order traversal while checking if:

leftNode <= currentNode < rightChild

If that check is ever violated, we immediately return a false value.

public static int last_printed = Integer.MIN_VALUE;
public static boolean checkBST(BinarySearchTree t){

    if(t == null) return true;

    // check / recurse left
    if(!checkBST(t.leftChild)) return false;

    //check current
    if(t.value <= last_printed) return false;
  
    // check / recurse right
    if(!checkBST(t.rightChild)) return false;

    return true; // DONE!

}
Advertisements