DEV Community

loading...

Interview Prep: Implementing A Binary Tree

kuddleman profile image Donny ・5 min read

Welcome back to interview prep. This week, we’ll build on last week’s intro to tree data structures and we’ll actually implement or build a binary tree in Java.

If you’ve never heard of the tree data structure, check out last week’s article to get up to speed:

Read about the Basics Here

Our Problem

We’re given a picture of a tree data structure the looks like this:

Alt Text

We are asked to code this tree out in Java.

Left and Right

We’ll just need a bit of additional terminology to accomplish our task. Note that each parent has 2 children. We can say that one child is on the “left” side of the parent and one is on the “right” side.

For example, in our image of a tree above, we see that the root is the node containing the value “1”. Its left child is “2” and its right child is “3”.

To simplify our language, instead of referring to the child nodes, we can refer just to the edges (lines) that lead from the parent to the child. Thus, we can say node 1’s right edge (or just “right) leads to node 3. Node 1’s left edge (or just “left”) leads to node 2.

With that knowledge, let’s begin to code

Let’s start by declaring a BinaryTree class and a main class:


public class BinaryTree{

    public static void main(String[] args) {

    }
}

Enter fullscreen mode Exit fullscreen mode

Then we’ll need a private field to hold our entry point to our tree. That entry point is called the “root”. Let’s declare that field as a TreeNode type (we’ll write the TreeNode class next).


public class BinaryTree{

    private TreeNode root;

    public static void main(String[] args) {

    }
}

Enter fullscreen mode Exit fullscreen mode

We’ve declared our root note as a TreeNode class type, so we better write that TreeNode class.

TreeNode is the class that will produce all the individual nodes we need to construct our binary tree.

We’ll have to supply each TreeNode with three items: 1) a left edge (we’ll just call it “left”); 2) a right edge (named “right”) and a variable we’ll call “variable” to store the node’s data. We’ll assume our binary tree can only contain integers as data for simplicity’s sake.


public class BinaryTree{

    private TreeNode root;

    private class TreeNode{
        private TreeNode left;  // left edge
        private TreeNode right; // right edge
        private int data;    //  here is where the data goes
    }

    public static void main(String[] args) {

    }
}

Enter fullscreen mode Exit fullscreen mode

Let’s add a constructor method below our field declarations in our TreeNode class. This constructor will just take as a parameter the data we want to insert into the node we’re creating.


public class BinaryTree{

    private TreeNode root;

    private class TreeNode{
        private TreeNode left;  // left edge
        private TreeNode right; // right edge
        private int data;    //  here is where the data goes

        public TreeNode(int data) {
             this.data = data;
        }
    }

    public static void main(String[] args) {

    }
}

Enter fullscreen mode Exit fullscreen mode

We’re ready now to create our tree. Below the TreeNode class, still within our BinaryTree class, let’s make a createBinaryTree method and within that method, let’s create a few nodes. We’ll create those nodes by creating instances of our TreeNode class:


public class BinaryTree{

    private TreeNode root;

    private class TreeNode{
        private TreeNode left;  // left edge
        private TreeNode right; // right edge
        private int data;    //  here is where the data goes

        public TreeNode(int data) {
             this.data = data;
        }
    }

   public void createBinaryTree() {

       TreeNode first = newTreeNode(1);
     //I’m create a TreeNode and calling it “first”
           // then I’m assigning the integer “1” as its value

    // Below: create more TreeNodes:
     TreeNode first = newTreeNode(2);
     TreeNode first = newTreeNode(3);
     TreeNode first = newTreeNode(4);
     TreeNode first = newTreeNode(5);
     TreeNode first = newTreeNode(6);
     TreeNode first = newTreeNode(7);

   }

    public static void main(String[] args) {

    }
}

Enter fullscreen mode Exit fullscreen mode

Let’s start organizing these nodes we’ve just created.
We have a field we already declared as “root”. By looking at the diagram of our tree(scroll to the top of this article to see it) we see we want the “1” node as the root. We also see from the diagram that the root node’s “left” edge will have the 2 node. Root’s right edge will have the 3 node. Let’s code that. (For simplicity’s sake, I’ll just show the createBinaryTree method here instead of the whole class)


public void createBinaryTree() {

       TreeNode first = newTreeNode(1);
     //I’m create a TreeNode and calling it “first”
           // then I’m assigning the integer “1” as its value

    // Below: create more TreeNodes:
     TreeNode first = newTreeNode(2);
     TreeNode first = newTreeNode(3);
     TreeNode first = newTreeNode(4);
     TreeNode first = newTreeNode(5);
     TreeNode first = newTreeNode(6);
     TreeNode first = newTreeNode(7);

     // we want our root to be assigned to “first”
     root = first;

     //we know root’s left edge is the 2 node:
     first.left = second;
   // root’s right edge is the 3 node:
   first.right = third;

   }


Enter fullscreen mode Exit fullscreen mode

Let’s finish it up. We see from our original diagram that the 2 node’s (AKA second) left edge points to the 4 node. It’s right edge points to the 5 node.

It’s similar for our 3 node (AKA third): third’s left is 6. Third’s right is 7:

public void createBinaryTree() {

       TreeNode first = newTreeNode(1);
     //I’m create a TreeNode and calling it “first”
           // then I’m assigning the integer “1” as its value

    // Below: create more TreeNodes:
     TreeNode first = newTreeNode(2);
     TreeNode first = newTreeNode(3);
     TreeNode first = newTreeNode(4);
     TreeNode first = newTreeNode(5);
     TreeNode first = newTreeNode(6);
     TreeNode first = newTreeNode(7);


     root = first;


     first.left = second;

   first.right = third;

   //second’s left node is 4
   second.left = fourth;

   //second’s right node is 5
   second.right = fifth;

   //Last two nodes to place:
   third.left = sixth;
   third.right = seventh;

   }


Enter fullscreen mode Exit fullscreen mode

And there is your binary tree implementation in Java. Admittedly, this is a simple implementation and there are fancier ways of doing this. For example, you could start with an array of data and then implement the tree using that array. However, as my dance teacher told me, “You have to learn the basic step first before you try any variations.”

By the way, if you look at our original diagram one last time, what if your interviewer asks you, “Ok, but what do the nodes containing the values 4, 5, 6, 7 point to?” Be sure to use the technical word to answer this question. So instead of saying, “Well, they point to ‘zip’”, you can say, “They point to null.”

Enjoy the adventure,

and keep coding out your dreams!

Namaste!

Discussion

pic
Editor guide