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;
}

}

A Basic Implementation of Generic Tree in Java

A generic tree data structure can be implemented in Java with the concept of an object to define a node and the object itself having a reference to n children nodes (or null to point the tree termination i.e. Leaf Nodes).

The following is a very trivial implementation of this data structure to show the concept of generic tree. The use of an array is completely voluntary, you can use any other datastructure of your choice to hold the children based on your need (Such as ArrayList or even LinkedLists).

This code any any other codes published in this blog are also available at Github (search for icodejava)

package com.icodejava.blog.published.datastructure;

/**
 * 
 * @author Kushal Paudyal www.icodejava.com Created On - Dec 5, 2016 Last
 *         Modified On - Dec 5, 2016
 * 
 *         This class shows a basic implementation of Generic Tree concept in
 *         Java.
 */
public abstract class AbstractGenericTreeNode {

	private AbstractGenericTreeNode [] children;

	public AbstractGenericTreeNode [] getChildren() {
		return children;
	}

	public void setChildren(AbstractGenericTreeNode [] children) {
		this.children = children;
	}
	
	public int getNumberOfChildren () {
		
		return children != null ? children.length : 0;
	}
	
}

The following is a concrete implementation of the Abstract node above and is defined to hold integer values. You however can implement this class to hold the object of your choice.

package com.icodejava.blog.published.datastructure;

/**
 * 
 * @author Kushal Paudyal www.icodejava.com Created On - Dec 5, 2016 Last
 *         Modified On - Dec 5, 2016
 * 
 *         This class shows a basic implementation of Generic Tree concept in
 *         Java.
 */

public class IntegerTreeNode extends AbstractGenericTreeNode {
	private int value;

	public IntegerTreeNode(int value, AbstractGenericTreeNode[] children) {
		super();
		this.value = value;
		this.setChildren(children);
	}

	public int getValue() {
		return value;
	}

}

Generic trees are different from Binary Trees. Binary Trees have 2 child nodes at maximum whereas the generic trees can have n-number of children.

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