Binary Trees in Java 2

Binary Trees in JavaWelcome 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";
		 */

	}

}

17 Responses to “Binary Trees in Java 2”

  1. fong1988 says:

    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!

  2. Vivek says:

    Line
    253 parent.rightChild = focusNode.leftChild;

    Shouldn’t it be:

    parent.rightChild = focusNode.rightChild;

    (As focusNode.leftChild is null )?

  3. PJ says:

    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

  4. David Troy says:

    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.

  5. Michael says:

    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

  6. Essey says:

    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!

    • Derek Banas says:

      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

  7. Essey says:

    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

    • Derek Banas says:

      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.

  8. Paul says:

    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.

Leave a Reply

Your email address will not be published.

Google+