Binary trees, a coding interview must-know

Here is the written code.

Introduction

After learning ReactJS and memorising your Starbucks order you feel fit for your first job as a software-dev, so you write an application and send it off to silicon valley. Soon enough, you receive and E Mail back from Meta, that you have been invited to a job interview. They tell you to bring your laptop because they want to see you code in an Object Oriented Language. The initial state of euphoria soon wears off as you realise that the all-seeing eye of Sauron demands to see you live in action and there is a realistic chance he will want to see binary trees.

If you see yourself in that situation, fear no more, I come to your rescue.

What is a binary tree

A binary tree is an important data structure where we have nodes, which contain data. Those nodes have (at max) two children, which also hold values and children. Important to note is, that those children are not placed randomly. How they are placed is as follows: If the new value is bigger than the last node, we put it to the right, otherwise we put it to the left. That's how we store values in a way where we also know where those values will be when we search through them. An example of how that could look:

How do we search a value?

Imagine we have following tree:

When we try to search for a value we realise what binary trees excel at (or why they are blazingly fast, for every "modern" dev). Let's check if and where value 7 is stored in our tree. We start at the first node which holds the value 8, and check if our searched value is bigger or smaller than it. It's smaller so we move left. There we find 6. Our value is bigger than 6 so we move right and there it is, our searched value.

How are the values added?

To be able to use our search algorithm, we will also need to implement a special way on how to insert values at the correct place, otherwise our algorithm won't be of any use. Let's use our tree from before and just add the value 12:

There we do the same as we did to find the value. We start at 8, move right and arrive at 16. There we move left because it is smaller. Now we are at 13, which has no children to its left, or where we would need to go. That means, that we insert it to the left of the 13.

Let's implement that in Java

After understanding this important theory you ask yourself: "Dude, just get to the point.", and I will now. I use VSCode, where I created a new Java project. In there I created two new classes: Node.java and BinaryTree.java.

Node

Let's begin by implementing the simpler part: Our node. That class will hold 3 attributes: its left child, its right child and its value. The children have the type Node, while the value will hold an int in our case:

public class Node {
    Node leftChild;
    Node rightChild;
    int value;

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

    // Getter and setter   
}

Tree

Next we will write our BinaryTree.java. That only holds 1 attribute: Node root. It's implementation looks as follows:

public class BinaryTree {
   Node root;

    public BinaryTree() {
         this.root = null;
    }

    // Getter and setter
}

And that we initialise in our main function:

public class App {
    public static void main(String[] args) throws Exception {
        BinaryTree tree = new BinaryTree();
        tree.setRoot(new Node(10));
    }
}

Implementing the add node algorithm

You maybe realised, that we can't add values yet. We will implement that next. Let's create a function in our binary tree called appendNode. Now what exactly does that function need to do? It first needs to go to the root node, check if the value is smaller or bigger and then go to one of the children, depending on if it's bigger or smaller. Usually the left side holds smaller children. If our value to be added is the same as a node, we can go either side. It has no relevance as long as we stay consistent. I chose to count equal values as bigger:

public Node appendNode(int value, Node node) {
    if (node.value > value) {
        appendNode(value, node.leftChild);
    } else {
        appendNode(value, node.rightChild);
    }
}

We will also return our newly created Node in the end, that's why I chose that return type.
What would happen if we run this function now? It would just recursively run trough and never come to a stop. To prevent that we need to implement the next feature: realise when its done searching for a free space. We achieve that by putting an if-statement that checks if that child node is null. If that's the case we found it and can set it as that child:

public Node appendNode(int value, Node node) {
    if (node.value > value) {
        if (node.leftChild == null) {
            node.setLeftChild(new Node(value));
            return node.leftChild;
        } else {
            appendNode(value, node.leftChild);
        }
    } else {
        if (node.rightChild == null) {
            node.setRightChild(new Node(value));
            return node.rightChild;
        } else {
            appendNode(value, node.rightChild);
        }
    }
    return null;
}

The return null; is just there to satisfy the compiler, it can never be reached.
Lastly, we have to think about what our initial value for our node is. To make it more comfortable to use it, we want to allow null and set the root manually. We can implement that with a simple null check:

public Node appendNode(int value, Node node) {
    if (node == null) {
        node = this.root;
    }
    // ...
}

We can check if it works by calling the function with the value 4 and checking the value of the roots leftChild:

public class App {
    public static void main(String[] args) throws Exception {
        BinaryTree tree = new BinaryTree();
        tree.setRoot(new Node(10));
        tree.appendNode(4, null);
        System.out.println(tree.getRoot().getLeftChild().getValue());
    }
}

This should print 4, which it does. We can also rebuild the tree from above now and check if 12 is where it should be:

public class App {
    public static void main(String[] args) throws Exception {
        BinaryTree tree = new BinaryTree();
        tree.setRoot(new Node(8));
        tree.appendNode(6, null);
        tree.appendNode(3, null);
        tree.appendNode(7, null);
        tree.appendNode(16, null);
        tree.appendNode(13, null);
        tree.appendNode(23, null);
        tree.appendNode(14, null);
        // Our last node:
        tree.appendNode(12, null);
        // If we want to check if its at the same place:
        System.out.println(tree.getRoot().getRightChild().getLeftChild().getLeftChild().getValue());
    }
}

That prints 12, which means the algorithm does work as it should.

Implementing the value search

The search is very similar to our algorithm where we added nodes, but now we search for them. Step one is, once again, to check if our value is bigger or smaller than the current nodes value:

public Node searchByValue(int value, Node node) {
    if (node.value > value) {
        searchByValue(value, node.leftChild);
    } else {
        searchByValue(value, node.rightChild);
    }
}

Now we also need to add a check for if it is the same. In that case we will need to return the value:

public Node searchByValue(int value, Node node) {
    if (node.value == value) {
        return node;
    } else if (node.value > value) {
        searchByValue(value, node.leftChild);
    } else {
        searchByValue(value, node.rightChild);
    }
}

In the case that the child we are trying to get is null, we know that the value does not exist, so we can return null:

public Node searchByValue(int value, Node node) {
    if (node.value == value) {
        return node;
    } else if (node.value > value) {
        if (node.leftChild == null) {
            return null
        }
        searchByValue(value, node.leftChild);
    } else {
        if (node.rightChild == null) {
            return null
        }
        searchByValue(value, node.rightChild);
    }
}

Now we do the last cleanup, which is setting the node to root if it is null and returning the return value from searchByValue:

public Node searchByValue(int value, Node node) {
    if (node == null) {
        node = this.root
    }

    if (node.value == value) {
        return node;
    } else if (node.value > value) {
        if (node.leftChild == null) {
            return null
        }
        return searchByValue(value, node.leftChild);
    } else {
        if (node.rightChild == null) {
            return null
        }
        return searchByValue(value, node.rightChild);
    }
}

Now if we run it for our binary tree from before:

public class App {
    public static void main(String[] args) throws Exception {
        BinaryTree tree = new BinaryTree();
        tree.setRoot(new Node(8));
        tree.appendNode(6, null);
        tree.appendNode(3, null);
        tree.appendNode(7, null);
        tree.appendNode(16, null);
        tree.appendNode(13, null);
        tree.appendNode(23, null);
        tree.appendNode(14, null);
        tree.appendNode(12, null);
        System.out.println(tree.searchByValue(12, null));
    }
}

We get following output (assuming you also generated a toString method):

{
    leftChild='null',
    rightChild='null',
    value='12'
}

Next steps (or conclusion)

Now that you don't have to fear any Corporate CEO's lizard eyes watching you make mistakes while implementing binary trees you are a big step closer to scoring your first silicon valley position. But there is still a lot of work ahead. There will probably be a few more articles like these about other coding interview topics, so stay tuned and happy hacking!