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:
Our Problem
We’re given a picture of a tree data structure the looks like this:
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) {
}
}
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) {
}
}
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) {
}
}
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) {
}
}
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) {
}
}
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;
}
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;
}
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!
Top comments (0)