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.

Rotating a two dimensional integer array In-Place and using extra memory

A 3×3 Two dimensional matrix

This is one of the popular interview questions. Interviewees are asked to rotate to the right or to the left an array. Make sure you ask the right question before you begin:

  • What kind of array are you rotating (Integer/ String / Objects?)
  • Do you want the rotation to be in place? (In case there is no extra memory available)
  • Or do you have extra space to do the rotation?

I have used integer array for rotation. However, you should be able to modify it for other data types easily. The example below does rotations using two ways:

  • In-place
  • Using extra space

I tried to calculate the time taken to do the rotation, but with my high end laptop, the time taken to rotate a 4×4 array was below zero ms. It could be different on your machine depending on the speed of your computing device.

Java Implementation:

package com.icodejava.blog.datastructure;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Mar 1, 2014
 * Last Modified On - Mar 1, 2014
 */
public class Matrix2DRotate {

	static int[][] twoDimensionalArray = new int[][]
			{ { 1, 2, 3, 4 },
			{ 5, 6, 7, 8 },
			{ 9, 10, 11, 12 },
			{ 13, 14, 15, 16 }

	};

	public static void main(String[] args) {

		System.out.println("\n\nINPUT ARRAY");

		printTwoDimensionalArray(twoDimensionalArray);

		System.out.print("\n\nROTATED WITH EXTRA SPACE:");

		int[][] rotatedArray = rotate2DArray(twoDimensionalArray);

		printTwoDimensionalArray(rotatedArray);

		System.out.print("\n\nROTATED WITH IN PLACE ROTATION:");

		rotatedArray = rotateInPlace(twoDimensionalArray, 4);

		printTwoDimensionalArray(rotatedArray);
	}

	/**
	 * @param array - two dimensional array
	 * @return Array rotated to right using extra space.
	 */
	private static int[][] rotate2DArray(int[][] array) {
		long startTime = System.currentTimeMillis();
		int length = array[0].length;
		int[][] tempArray = new int[length][length];

		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				tempArray[i][j] = array[length - 1 - j][i];
			}

		}

		long endTime = System.currentTimeMillis();
		printTimeTaken(startTime, endTime);

		return tempArray;
	}

	private static void printTimeTaken(long startTime, long endTime) {

		// System.out.print("StartTime: " + startTime +" endTime: " + endTime);

		if (startTime <= 0 || endTime <= 0 || startTime > endTime) {
			return;
		}

		System.out.println("Took " + (endTime - startTime) + " ms");

	}

	/**
	 * This method rotates a two dimensional matrix in layers.
	 * Portion of this code is taken from Cracking The Coding Interview Book
	 * @param matrix - Two Dimensional Matrix
	 * @param size - size of Matrix
	 * @return In Place Rotated Matrix
	 */
	public static int[][] rotateInPlace(int[][] matrix, int size) {

		long startTime = System.currentTimeMillis();

		for (int layer = 0; layer < size / 2; ++layer) {

			int first = layer;
			int last = size - 1 - layer;

			for (int i = first; i < last; ++i) { 				int offset = i - first; 			 				//Saves the top value 				int top = matrix[first][i];  				 				// left -> top
				matrix[first][i] = matrix[last - offset][first];

				// bottom -> left
				matrix[last - offset][first] = matrix[last][last - offset];

				// right -> bottom
				matrix[last][last - offset] = matrix[i][last];

				// top -> right
				matrix[i][last] = top; // right 			}
		}

		long endTime = System.currentTimeMillis();
		printTimeTaken(startTime, endTime);

		return matrix;
	}

	/**
	 * This method prints the two dimensional array to System Console
	 */
	private static void printTwoDimensionalArray(int[][] intArray) {
		for (int i = 0; i < intArray[0].length; i++) {
			for (int j = 0; j < intArray[i].length; j++) {
				System.out.print(intArray[i][j] + "\t");
			}
			System.out.println();
		}

	}
}

Output of running above program:

INPUT ARRAY
1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

ROTATED WITH EXTRA SPACE:Took 0 ms
13	9	5	1
14	10	6	2
15	11	7	3
16	12	8	4

ROTATED WITH IN PLACE ROTATION:Took 0 ms
13	9	5	1
14	10	6	2
15	11	7	3
16	12	8	4

Sorted Circular Linked List Implementation And Insert Operation

Circular Linked List Data Structure (Unsorted). Source: Wikipedia

Circular Linked List is a kind of Linked List where the elements are accessed sequentially and the last node of the sequence points back to the first node, thus creating a circle. Circular linked lists can be created with simple Java Objects. The only tricky portion is to understand how to link the next element.

The following piece of code demonstrates:

  1. How to create a circular linked list data structure
  2. How to insert elements to the list so that the insertion creates a sorted data structure.
  3. How to handle special scenarios such as:
    • Inserting to an empty list
    • Inserting duplicate elements
    • Inserting element smaller than head (thus forming new head)
    • Inserting element greater than tail (thus forming new tail)
    • Inserting element in between two elements.

package com.icodejava.blog.datastructure;
/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Feb 22, 2014
 * Last Modified On - Feb 22, 2014
 */
public class CircularListInsert {
	public static void main(String args[]) {

		CircularList myList = new CircularList(5);
		myList.printAll();
		
		myList = myList.insert(2);
		myList.printAll();
		
		//test for value smaller than the head.
		myList = myList.insert(1);
		myList.printAll();
		
		myList = myList.insert(3);
		myList.printAll();
		
		//Test for duplicate value
		myList = myList.insert(5);
		myList.printAll();
		
		//test for value greater than he tail.
		myList = myList.insert(6);
		myList.printAll();
	}
}

class CircularList {
	CircularList next;
	int value;

	public CircularList(int value) {
		this.next = this;
		this.value = value;
	}

	/**
	 * @param value
	 *            - new value to be inserted in the list.
	 * @return head node in the circular list
	 * 
	 * This method inserts data in ascending order.
	 */
	public CircularList insert(int value) {

		// if the current list is null.
		if (this == null) {
			return new CircularList(value);
		} else if (this.next == this) {
			// if the current list is head and tail i.e. single element
			this.next = new CircularList(value);
			this.next.next = this;

			// return the smallest node as the head
			if (this.value < value) {
				return this;
			} else {
				return this.next;
			}
		} else if (value < this.value) {

			// if the value is smaller than the head
			// find the tail and append.

			CircularList temp = new CircularList(value);
			temp.next = this;

			CircularList current = this.next;
			while (current.next != this) {
				current = current.next;
			}

			current.next = new CircularList(value);
			current.next.next = this;

			return current.next;

		} else if (value >= this.value) {
			CircularList current = this;

			/**
			 * Keep looking for nodes until all the nodes are smaller than the
			 * value to be inserted.
			 */
			while (current.next != this && current.next.value <= value) {
				current = current.next;
			}

			/**
			 * Once we find the node to be inserted, make a copy of the
			 * current's next value. Insert a node as current's next. and Make
			 * current's next's next value as the previous next which has been
			 * copied as temp
			 */
			CircularList temp = current.next;
			current.next = new CircularList(value);
			current.next.next = temp;
			return this;

		}

		return this;
	}

	public void printAll() {

		if (this == null) {
			return;
		}

		CircularList current = this;
		
		do {

			System.out.print(current.value + ",");
			current = current.next;
		} while (current != this);

		System.out.println();
	}
}


The output of running this program is below. Please note that the elements appear sorted.

5,
2,5,
1,2,5,
1,2,3,5,
1,2,3,5,5,
1,2,3,5,5,6,