A Basic Implementation of Binary Tree in Java

A Binary Tree simply can be defined in Java as a node that holds a value for itself and holds reference to a left child node and a right child node. The binary tree can have nodes that have a maximum of 2 children. As you can see in the example below, I have defined the value to be of type Comparable, so that it can be any object that can be compare for less than, greater than or equals. However, if you are going to only store either integers or Strings, for example, you can change the data type to int or String as needed.

The following is a very simple implementation of this concept.

Note: – if the binary tree has left nodes only or right nodes only, it becomes a singly linked list.

package com.icodejava.blog.published.datastructure;
/**
* @author Kushal Paudyal
* Created on 12/5/2016
* Last Modified on 12/5/2016
*
* Binary Tree Node representation.
* - Node has a value, a left node and a right node.
* - Single node, when created, has left and right node as null.
*/
@SuppressWarnings("rawtypes")
class BinaryTreeNode {
Comparable value;
BinaryTreeNode left;
BinaryTreeNode right;

public BinaryTreeNode(Comparable value) {
this.value = value;
this.left = null;
this.right = null;
}

public Comparable getValue() {
return value;
}

public void setValue(Comparable value) {
this.value = value;
}

public BinaryTreeNode getLeft() {
return left;
}

public void setLeft(BinaryTreeNode left) {
this.left = left;
}

public BinaryTreeNode getRight() {
return right;
}

public void setRight(BinaryTreeNode right) {
this.right = right;
}

}

How to find the Lowest Common Ancestor (LCA) of two nodes in a Binary Tree

If you are given a binary tree and two nodes and you have to find the lowest common ancestor, you can use the following approach.

  1. If the binary tree itself is null, you don’t have any common ancestor. This is an error condition.
  2. If one of the two nodes is the root, then the root itself is the common ancestor.
  3. Otherwise, recursively start finding the ancestor on the left node and right node.
    • If Node a and Node b lie in the left, their Lowest Common Ancestor is in the left.
    • If Node a and Node b lie in the right,their Lowest Common Ancestor is in the right.
    • Otherwise, root is the Lowest common ancestor.

Java code to find the common ancestor of Binary Nodes

package com.icodejava.blog;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Mar 13, 2014
 * Last Modified On - Mar 13, 2014
 */
public class LowestCommonAncestorBinaryTree {
	
	public static void main(String args[]) {
		/**
		 * Create a sample Binary Tree. A Binary tree does not have to maintain
		 * left <root < right relationship.
		 */
		Node root = new Node(1);
		root.left = new Node(2);
		root.right = new Node(4);
		root.left.left = new Node(6);
		root.left.right = new Node(5);

		root.right.left = new Node(9);
		root.right.right = new Node(11);
		root.right.right.left = new Node(7);
		root.right.right.right = new Node(3);

		System.out.println("Lowest Common Ancestor of Node 3 and 9 is: "
				+ findLowestCommonAncestor(root, root.right.right.right, root.right.left).value);
		
		System.out.println("Lowest Common Ancestor of Node 3 and null is: "
				+ findLowestCommonAncestor(root, root.right.right.right, null).value);
		
		System.out.println("Lowest Common Ancestor of Node 11 and null is: "
				+ findLowestCommonAncestor(root, root.right.right, null).value);

	}
	
	/**
	 * Recursive approach to find the Lowest Common Ancestor
	 * @param root
	 * @param a - first Node
	 * @param b - second Node
	 * @return Node that is lowest common ancestor of both a and b
	 */
	public static Node findLowestCommonAncestor(Node root, Node a, Node b) {

		Node left = null;
		Node right = null;

		if (root == null) {
			return null;
		}

		/**
		 * If Node a or Node b is also the root, then the root itself is lowest common ancestor
		 */
		if (root == a || root == b) {
			return root;
		}

		left = findLowestCommonAncestor(root.left, a, b);
		right = findLowestCommonAncestor(root.right, a, b);

		/**
		 * If Node a and Node b lie in the left, their Lowest Common Ancestor is in the left.
		 * If Node a and Node b lie in the right,their Lowest Common Ancestor is in the right.
		 * 
		 * Otherwise, root is the Lowest common ancestor.
		 */
		if (left != null && right != null) {
			return root;
		}

		return (left != null) ? left : right;
	}
}
/**
 * Binary Tree representation.
 */
class Node {
	Node left;
	Node right;
	int value;
	
	public Node(int value) {
		left = null;
		right = null;
		this.value = value;
	}
}

The output of running above program is:

Lowest Common Ancestor of Node 3 and 9 is: 4
Lowest Common Ancestor of Node 3 and null is: 3
Lowest Common Ancestor of Node 11 and null is: 11

Binary Tree Representation and Tree Traversal (In-Order, Pre-Order, Post-Order)

Binary Tree

What is a Binary Tree?
A binary tree is a tree data structure in which each node has at most two children (referred to as the left child and the right child). In a binary tree, the degree of each node can be at most two.

A single node in binary tree can be represented by a node itself and having left and right children as null. When there are two ore more, it starts becoming a tree like structure. Nodes other than root, are added either as a right child or as a left child of another node including root node.

Time Complexity:

  1. Insert Erase – O(h) where h = height
  2. Lookup / Indexing – O(h)
  3. Find – O(h)

In a worst case scenario, N = h, in a best case scenario, h = log(N).

Here is a simple representation of a binary tree in Java.

/**
 * Binary Tree Node representation.
 * - Node has a value, a left node and a right node.
 * - Single node, when created, has left and right node as null.
 */
@SuppressWarnings("rawtypes")
public class BinaryTreeNode {
	Comparable value;
	BinaryTreeNode left;
	BinaryTreeNode right;

	public BinaryTreeNode(Comparable value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}

}


Tree Traversal:
There are three popular binary tree traversal algorithms:

  • Pre-Order Traversal
    • Visit the root node
    • Traverse left subtree
    • Traverse right subtree
  • In-order Traversal
    • Traverse left subtree
    • Visit the root node
    • Traverse right subtree
  • Post-order Traversal
    • Traverse left subtree
    • Traverse right subtree
    • Visit the node

Java Implementation of Binary Tree and the three tree traversals:

package com.icodejava.blog;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Mar 3, 2014
 * Last Modified On - Mar 3, 2014
 */
public class BinaryTreeTraversal {
	public static void main(String args[]) {

		BinaryTreeNode root = createBinaryTree();

		System.out.println("IN ORDER TREE TRAVERSAL");
		// In Order Tree Traversal - LEFT - ROOT - RIGHT.
		traverseInOrder(root);

		System.out.println("\n\nPRE ORDER TREE TRAVERSAL");

		// Pre-Order Tree Traversal - ROOT - LEFT - RIGHT.
		traversePreOrder(root);

		System.out.println("\n\nPOST ORDER TREE TRAVERSAL");

		// Post Order Tree Traversal - LEFT - RIGHT - ROOT.
		traversePostOrder(root);
	}

	private static BinaryTreeNode createBinaryTree() {
		// Creating a tree with following data. Root node being 15.
		// 15,5,3,12,13,10,6,7,16,20,18,23.
		BinaryTreeNode root = new BinaryTreeNode(15);
		addNode(root, 5);
		addNode(root, 3);
		addNode(root, 12);
		addNode(root, 13);
		addNode(root, 10);
		addNode(root, 6);
		addNode(root, 7);
		addNode(root, 16);
		addNode(root, 20);
		addNode(root, 18);
		addNode(root, 23);
		return root;
	}

	@SuppressWarnings({ "unchecked", "rawtypes" })
	public static BinaryTreeNode addNode(BinaryTreeNode root, Comparable value) {
		//if root is null
		if(root == null) {
			return new BinaryTreeNode(value);
		}

		//if the value is smaller than a node,
		if(value.compareTo(root.value) < 0) {
			root.left = addNode(root.left, value);
		} else {
			root.right = addNode(root.right, value);
		}

		return root;
	}

	/**
	 * IN-ORDER Traversal - Recursively Traverses LEFT-ROOT-RIGHT
	 * In order traversal results sorted order traverse.
	 */
	public static void traverseInOrder(BinaryTreeNode theRootNode) {

		if (theRootNode != null) {
			// left
			traverseInOrder(theRootNode.left);
			// root
			System.out.print(theRootNode.value + ",");
			// right
			traverseInOrder(theRootNode.right);
		}
	}

	/**
	 * PRE-ORDER Traversal - Recursively Traverses ROOT-LEFT-RIGHT
	 */
	public static void traversePreOrder(BinaryTreeNode theRootNode) {

		if (theRootNode != null) {
			//root
			System.out.print(theRootNode.value + ",");

			//left
			traversePreOrder(theRootNode.left);

			//right
			traversePreOrder(theRootNode.right);
		}
	}

	/**
	 * POST ORDER Traversal - Recursively traverses LEFT-RIGHT-ROOT
	 */
	public static void traversePostOrder(BinaryTreeNode theRootNode) {

		if (theRootNode != null) {
			//left
			traversePostOrder(theRootNode.left);

			//right
			traversePostOrder(theRootNode.right);

			//root
			System.out.print(theRootNode.value + ",");

		}
	}

}

/**
 * Binary Tree Node representation.
 * - Node has a value, a left node and a right node.
 * - Single node, when created, has left and right node as null.
 */
@SuppressWarnings("rawtypes")
class BinaryTreeNode {
	Comparable value;
	BinaryTreeNode left;
	BinaryTreeNode right;

	public BinaryTreeNode(Comparable value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}

}

Output of running the above program:

IN ORDER TREE TRAVERSAL
3,5,6,7,10,12,13,15,16,18,20,23,

PRE ORDER TREE TRAVERSAL
15,5,3,12,10,6,7,13,16,20,18,23,

POST ORDER TREE TRAVERSAL
3,7,6,10,13,12,5,18,23,20,16,15,