Binary Trees in Java 2
Welcome to my 2nd video on Binary Trees in Java. If you haven’t seen part 1, definitely watch it first or this will be confusing binary tree in Java.
In this part of the tutorial, I will take you step-by-step through the process of deleting nodes in a binary tree. This topic seems to be confusing to many people. I personally prefer to build trees with the builder design pattern like I showed here Encapsulate Composite with Builder, but it is also important to understand the basics of the binary tree.
If you like videos like this, it helps to tell Google+ with a click here
Code From the Video
Binary Trees 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
preorderTraverseTree(focusNode.leftChild);
// Visit the currently focused on node
System.out.println(focusNode);
// Traverse the right node
preorderTraverseTree(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) {
preorderTraverseTree(focusNode.leftChild);
preorderTraverseTree(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 boolean remove(int key) {
// Start at the top of the tree
Node focusNode = root;
Node parent = root;
// When searching for a Node this will
// tell us whether to search to the
// right or left
boolean isItALeftChild = true;
// While we haven't found the Node
// keep looking
while (focusNode.key != key) {
parent = focusNode;
// If we should search to the left
if (key < focusNode.key) {
isItALeftChild = true;
// Shift the focus Node to the left child
focusNode = focusNode.leftChild;
} else {
// Greater than focus node so go to the right
isItALeftChild = false;
// Shift the focus Node to the right child
focusNode = focusNode.rightChild;
}
// The node wasn't found
if (focusNode == null)
return false;
}
// If Node doesn't have children delete it
if (focusNode.leftChild == null && focusNode.rightChild == null) {
// If root delete it
if (focusNode == root)
root = null;
// If it was marked as a left child
// of the parent delete it in its parent
else if (isItALeftChild)
parent.leftChild = null;
// Vice versa for the right child
else
parent.rightChild = null;
}
// If no right child
else if (focusNode.rightChild == null) {
if (focusNode == root)
root = focusNode.leftChild;
// If focus Node was on the left of parent
// move the focus Nodes left child up to the
// parent node
else if (isItALeftChild)
parent.leftChild = focusNode.leftChild;
// Vice versa for the right child
else
parent.rightChild = focusNode.leftChild;
}
// If no left child
else if (focusNode.leftChild == null) {
if (focusNode == root)
root = focusNode.rightChild;
// If focus Node was on the left of parent
// move the focus Nodes right child up to the
// parent node
else if (isItALeftChild)
parent.leftChild = focusNode.rightChild;
// Vice versa for the left child
else
parent.rightChild = focusNode.rightChild;
}
// Two children so I need to find the deleted nodes
// replacement
else {
Node replacement = getReplacementNode(focusNode);
// If the focusNode is root replace root
// with the replacement
if (focusNode == root)
root = replacement;
// If the deleted node was a left child
// make the replacement the left child
else if (isItALeftChild)
parent.leftChild = replacement;
// Vice versa if it was a right child
else
parent.rightChild = replacement;
replacement.leftChild = focusNode.leftChild;
}
return true;
}
public Node getReplacementNode(Node replacedNode) {
Node replacementParent = replacedNode;
Node replacement = replacedNode;
Node focusNode = replacedNode.rightChild;
// While there are no more left children
while (focusNode != null) {
replacementParent = replacement;
replacement = focusNode;
focusNode = focusNode.leftChild;
}
// If the replacement isn't the right child
// move the replacement into the parents
// leftChild slot and move the replaced nodes
// right child into the replacements rightChild
if (replacement != replacedNode.rightChild) {
replacementParent.leftChild = replacement.rightChild;
replacement.rightChild = replacedNode.rightChild;
}
return replacement;
}
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));
System.out.println("Remove Key 25");
theTree.remove(25);
System.out.println(theTree.findNode(25));
theTree.inOrderTraverseTree(theTree.root);
}
}
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 Derek,
I really enjoy your tutorials. They are the best that I have ever seen. Thank you very much for making those videos, which are super helpful!
I wonder in the near future if you plan to do some tutorials on java generics.
Thanks again!
Thank you 🙂 Yes I will fill in all of the topics I skipped over in the original Java tutorial. I’ll cover everything by the end
Line
253 parent.rightChild = focusNode.leftChild;
Shouldn’t it be:
parent.rightChild = focusNode.rightChild;
(As focusNode.leftChild is null )?
I meant:
Line 274 (As focusNode.leftChild is null )..
Shouldn’t it be:
parent.rightChild = focusNode.rightChild;
I went back and checked the code and you are correct. Sorry about the error. I fixed it. Thank you very much for pointing that out 🙂
Hi Derek,
Thank you so much for your excellent work!
The question I have is related to your code but not really related to the BinaryTree topic. I run your code on Eclipse and get error of “coudn’t find the main class, program exit”. It happened to several classes of mine recently and I don’t know why. Can you help me with this?
Thank you!
PJ
Hi PJ,
Check out Install Eclipse for Java. You need to save the code in the source folder in the project explorer.
Good day Derek,
Thank you so much for your wonderful tutorial!
I have a favor to ask about tutorial about a B-Tree or B+Tree?
If you can help me about it.
You’re very welcome 🙂 Thank you. Yes I will make an advanced algorithm tutorial very soon.
Great tutorial, but when you add the numbers in an odd order such as 80,25,40,45,75,2 and try to print the traverse in order it comes out as 25,2,40,45,75,2
I’ll take a look at that. Thank you for pointing it out
Hi Derek,
Your tutorials are excellent, explanatory and free..I am the #1 fan of your presentation style!
As I’m java beginner I face with a lot of questions, would you mind give me your email.
Thank you for your help!
Thank you 🙂 The best way to get me is to leave a message here, through a YouTube PM, or through a Google+ PM. My email account has been messed up. I get over 1000 emails a day. I’m always happy to help 🙂
Derek
Thank you for your quick reply, you’re awesome!
I have completed all your java video and java algorithms tutorials but i don’t know which one should i study next. Can you write me which order i have to follow, i have planned to finish all your video tutorials.
I am addicted to your tutorials!
essey
Thank you 🙂 They were made to watch in this order : Design Patterns, UML, Object Oriented Design, Refactoring, but you can do them in any order for the most part.
Excellent tutorial! However, I noticed that in your delete function you don’t check for a null root before entering the while loop. This can lead to an infinite loop if the user tries to delete any node while the list is empty.
I just inserted the simple
if (root == null)
{
return false;
}
in-between lines 171 and 175.
Thanks for the input. Sorry I missed that. i was writing out of my head.