Binary Tree in Java
Welcome to my tutorial on the Binary Tree in Java. On average a tree is more efficient then other data structures if you need to perform many different types of operations.
In this tutorial I’ll show you what a binary tree is, and how to create, add, traverse and find nodes. I’ll also explain all the terminology used when describing tree structures. We’ll cover nodes, paths (edges), traversing and much more.
If you like videos like this, it helps to tell Google+ with a click [googleplusone]
Code From the Video
Binary Tree in Java BinaryTree.java
public class BinaryTree {
Node root;
public void addNode(int key, String name) {
// 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 our new Node
Node parent;
while (true) {
// root is the top parent so we start
// there
parent = focusNode;
// Check if the new node should go on
// the left side of the parent node
if (key < focusNode.key) {
// Switch focus to the left child
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; // All Done
}
} else { // If we get here put the node on the right
focusNode = focusNode.rightChild;
// If the right child has no children
if (focusNode == null) {
// then place the new node on the right of it
parent.rightChild = newNode;
return; // All Done
}
}
}
}
}
// All nodes are visited in ascending order
// Recursion is used to go to one node and
// then go to its child nodes and so forth
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);
}
}
public void preorderTraverseTree(Node focusNode) {
if (focusNode != null) {
System.out.println(focusNode);
preorderTraverseTree(focusNode.leftChild);
preorderTraverseTree(focusNode.rightChild);
}
}
public void postOrderTraverseTree(Node focusNode) {
if (focusNode != null) {
postOrderTraverseTree(focusNode.leftChild);
postOrderTraverseTree(focusNode.rightChild);
System.out.println(focusNode);
}
}
public Node findNode(int key) {
// Start at the top of the tree
Node focusNode = root;
// While we haven't found the Node
// keep looking
while (focusNode.key != key) {
// If we should search to the left
if (key < focusNode.key) {
// Shift the focus Node to the left child
focusNode = focusNode.leftChild;
} else {
// Shift the focus Node to the right child
focusNode = focusNode.rightChild;
}
// The node wasn't found
if (focusNode == null)
return null;
}
return focusNode;
}
public static void main(String[] args) {
BinaryTree theTree = new BinaryTree();
theTree.addNode(50, "Boss");
theTree.addNode(25, "Vice President");
theTree.addNode(15, "Office Manager");
theTree.addNode(30, "Secretary");
theTree.addNode(75, "Sales Manager");
theTree.addNode(85, "Salesman 1");
// Different ways to traverse binary trees
// theTree.inOrderTraverseTree(theTree.root);
// theTree.preorderTraverseTree(theTree.root);
// theTree.postOrderTraverseTree(theTree.root);
// Find the node with key 75
System.out.println("\nNode with the key 75");
System.out.println(theTree.findNode(75));
}
}
class Node {
int key;
String name;
Node leftChild;
Node rightChild;
Node(int key, String name) {
this.key = key;
this.name = name;
}
public String toString() {
return name + " has the key " + key;
/*
* return name + " has the key " + key + "\nLeft Child: " + leftChild +
* "\nRight Child: " + rightChild + "\n";
*/
}
}
Hi Darek,
i didn’t yet covered all you ds videos but just curious to know, are you also gonna cover index search in depth?
I’m sorry, but I’m not sure what you mean. Can you provide an example?
Derek,
COMMENT: Your videos are incredible! Thank you for producing them and keep them coming. The pace is perfect and just the right amount of subject material for each one.
QUESTION: The binary tree examples will only work if there are no duplicate keys, correct?
SUGGESTION: I don’t want to make you change your format, but I would prefer it if you would skip the blank lines between lines of code, so that there would always be more code visible on the screen. It’s probably just me.
Thank you very much 🙂 Yes, a binary search tree doesn’t have duplicate nodes. I’m constantly trying to improve my videos and I calue the input. I’ll do my best to get more code on the screen at once.
Hello Derek, thanks for everything you have done! I just have one question. I see that in your node class you have made it so that every node has a reference to its left and right child. Don’t nodes also need references to their parent nodes?
Just a question… and thanks
You’re very welcome 🙂 I cover that later as the tutorial progresses. I should have mentioned that
Hi Derek,
I’m new to Java but having looked at this video I must stay.. The vid is awesome. Indeed very useful for a new starter like me.
Thanks
Hi, Thank you 🙂 I’m very happy that you found it useful. You’re very welcome
Awesome tutorial! Please keep up the great work!
Thank you 🙂 I have videos planned out over a year in advance. I look forward to the days in which I can make game tutorials while covering electronics. I have been working towards that goal for 5 years.
Hi sir i found the video very useful but i would be happy if u could lemme know how to find the path of a node in the tree which we are searching for……
Thank you 🙂 You may find the code in Binary Trees 2 to be useful. I hope that helps
I am new to Binary Tree and was sweating over it for couple of days, your videos are awesome. Perfect!!! Thanks a lot
Thank you 🙂 I’m glad it helped
In this code you sort them with integers, can you show a way to sort with strings instead?
You don’t really sort with strings because they have to be unique. I have a bunch of sorting videos on this page Java Algorithm Video Tutorial. I hope that helps
Comment
Response 🙂 Feel free to post comments. I can’t allow them to display immediately for security reasons, but I will answer all of them.
Hi Derek, Thanks for the article.
One question: Would it be helpful to know how to traverse the tree in order without using recursion? And, how would I go about doing that? Right now, I think i might have to use a stack since it seems like a depth first traversal but I am not sure on the intricacies. Would love to hear your thoughts.
Hi Pat,
I’m glad you found it useful. Using recursion is the normal way to traverse trees. You could do it in other ways, but I think this is the most straight forward.
Hello,
Very nice presentation and explanation of the code! I like it. However, you are talking about Binary Search Tree, which belongs to Binary Tree group. The students can be lost when we talk for ex. about Heap Tree which is also a Binary Tree but with other properties or AVL, Red-Black tree etc. Again – very good presentation, but can be misleading for the beginners.
Best wishes!
Sorry about that. I have changed the name of the video recently to avoid confusion.
Hey Derek, great tutorial. I do have one question though. How would you implement an 2 dimensional array into a tree? I’m having trouble trying to figure out how to implement a table of keys into a tree.
Thank you 🙂 I’ll be getting back into advanced algorithms soon. Why not add any addition information you need to store in the node class?
Hi Derek, Thank you for such a good explanation of this series.
Since I am still new to Java programming and binary tree, I could not understand why the root’s members can be updated with the value assigned to parent’s member even though you never declare “root = parent”?
When I went through debugging, I saw the left or right child of the root are replaced with the key assigned to parent’s child.
Thanks for video. It is good
You’re very welcome 🙂
Hi Derek ! Great tutorials overall.
However , I’d like to point out that your code is implementing a binary search tree and not a binary tree. A binary search tree is just a special case of a binary tree where the condition of left child being smaller than the node and right child being larger is satisfied.
Kindly update the title probably.
Thank you 🙂 Yes I did change the title of the video. I don’t know why I decided in the past the abbreviate the name. Sorry about that.
Hi Derek,
Thanks so much for the video. I was wondering if you could offer some guidance on how to implement a family tree using a Binary Tree. For this to work, how would I implement an Ancestor, partner, sibling – child?
Any help would be appreciated,
Thanks
You’re very welcome 🙂 Everything is dependent on keys with a binary tree. A family tree wouldn’t work very well because you only have 2 nodes coming off of each other node. Does that make sense?
Hello Derek. All you tutorials are excellent!
But here in this one I wonna to point you to some improvement.
In the addNode method there is no need to use extra ‘parent’ variable, you can survive with ‘focusNode’ only. Its quite important to have as clean implementation as possible especially with recursions when you need to model stack calls in your brains 🙂
Here my slightly simplified version:
public void addNode(int key, String value) {
Node newNode = new Node(key, value);
if(root == null) {
root = newNode;
} else {
Node focusNode = root;
while(true) {
if(key < focusNode.key) {
// left branch
if(focusNode.leftChild == null){
focusNode.leftChild = newNode;
return;
}
focusNode = focusNode.leftChild;
} else {
// right branch
if(focusNode.rightChild == null) {
focusNode.rightChild = newNode;
return;
}
focusNode = focusNode.rightChild;
}
}
}
}
Thank you very much for the input 🙂 I greatly appreciate it. I wrote most of this out of my head so it wasn’t optimized.
Sir, I would like to ask how can I display all of my inputs categorized if it belongs to the Right side or the Left side..
EX:
LeftSide
25
30
RightSide
15
75
(something like that sir)
I’m still learning and I’m kinda having a hard time figuring it out.
Thank you sir 🙂
I cover how to work through programming problems here. Maybe that will help?
thank you sir 🙂
another, how can I check if my binary tree is empty or not?
I’m currently thinking of writing a class isEmpty() to check whether my BST is empty or not before I proceed in removing some nodes.
And I dont know how 🙁
(I’m currently watching the 2nd part of your tutorial about Binary Tree)
thank you again Sir 🙂
To see if the tree is empty check if root is null. That’s all you need to do.
Almost finished with my codes sir 🙂
Thank you very much for your tutorial videos and quick responses Sir 🙂
It was really a great help~
God bless you sir 🙂
I’m happy to hear that. You’re very welcome 🙂 May God bless you as well.
The code doesn’t work. I get a java.lang.NoSuchMethodError in line 009.
You need to create the class Node. It is at the bottom of the page.
Awesome videos. I am a beginner with Java and these videos are very helpful
Thank you 🙂 I’m glad I can help.
Do you have a link to the video on youtube or another mirror? It seems to be missing for me….
It is showing now. Sorry YouTube must have been having trouble showing the video at the time.
Instead of finding the specific key, how would you display just the whole tree with the strings?
I show how to print trees in this example.
Hi i am wondering how a text file could be read into this example and update the values in the tree this way. Cheers
I cover how to read and write text files here. I hope it helps 🙂
Sir your tutorials are awesome…
I got a “B-” for OOPs Semester Examination in University of Colombo, Sri Lanka for Bachelor of IT…
I didn’t attend any classes for this… I just followed your video tutorials and now I’m keep going with your Java tutorials for next semester Java Examination….
Thanks a lot….
You are doing great job for us………………
I’ll keep watching your videos
That is very cool 🙂 I’m very happy to hear that the videos were that useful. Thanks for taking the time to tell me.
Hi Thanks for really taking time and helping others.
I do have really time experience of 8 yrs of programming experience, I still struggle to get the concepts of data structures and algorithms in the right.
This video did not only help me in clearly understand the concepts. It boasted my confidence a lot. I genuinely thankful for your videos.
Hopefully able to crack the coding interviews with the new arsenal in my kitty.
Allyn
Thank you Allyn 🙂 I’m very happy that I could help. Good luck on your interviews
Thanks. I am also looking into learning some material related to Graphs data structures. Do you have any ?
Allyn
Those videos will come out asap
I just Love your videos. It so quickly walks through the concepts.
Thank you 🙂
Good video,but you should have mentioned in the beginning of the video what do higher and lower values of keys have relationship with the Node hierarchy.
Sorry about that
Hi Derek,
Thank you for the great video explaining implementation of Binary Search Tree. I just need a clarification regarding the terminology. From my knowledge, A Binary Search Tree is different from Binary Tree with the condition that all the left node are less than or equal to root and the right nodes are greater than the root node.
Hi, Yes you are correct that this is the special form of a binary tree called a binary search tree
Hi !
loved the binary tree video!
just a question, how did you improve your programming?
I cant do a whole program on my own like you 🙁
any tips?
Thank you 🙂 Study my object oriented design, UML and refactoring tutorials. They will take you to the next level.
Hat’s off to you sir.
Thanks a lot.
Thank you 🙂 You’re very welcome
Awesome video
Thank you 🙂
When you try to find a node that isn’t in the tree, it throws a NullPointerException in main and findNode. Not sure why it does that in main, but I do understand why in findNode (obviously). Is there a way to correctly handle the exception?
Yes throw in an exception handler. Sorry I didn’t do that, but I didn’t want to distract from the idea