Finds the second largest element in an array within n + log(n)_base2 -2 comparisons

SecondLargest.java

import java.util.LinkedList;

/**
 * @author thiru
 *
 */
public class SecondLargest {

	private class TreeNode {
		int item;
		TreeNode left;
		TreeNode right;
		TreeNode parent;

		public TreeNode(int item, TreeNode left, TreeNode right, TreeNode parent) {
			this.item = item;
			this.left = left;
			this.right = right;
			this.parent = parent;
		}
	}

	private TreeNode root;
	private int comparisons;

	private TreeNode getMaxNode(TreeNode root) {
		//If I'm the leaf node return myself
		if(root.left == null && root.right == null)
			return (TreeNode) root;
		else {
			TreeNode leftMax = getMaxNode((TreeNode) root.left);
			TreeNode rightMax = getMaxNode((TreeNode) root.right);

			// Keep track of number of comparisons
			comparisons++;
			if(leftMax.item > rightMax.item) {
				root.item = leftMax.item;
				// Return the largest value
				return leftMax;
			}
			else {
				root.item = rightMax.item;
				// return the largest
				return rightMax;
			}
		}
	}

	public void compute() {

		// Keep track of comparisons
		comparisons = 0;
		System.out.print("Before getting max: ");
		levelOrder(this.root);
		TreeNode maxNode = getMaxNode(this.root);
		System.out.print("After getting max:  ");
		levelOrder(this.root);

		// Find my second largest node
		TreeNode tempNode = maxNode.parent;
		TreeNode brotherNode = getBrotherNode(maxNode);
		while(tempNode.parent != null) {
			//get brother
			TreeNode tempNode2 = getBrotherNode(tempNode);
			//see if this loser is greater than my older loser
			comparisons++;
			if(tempNode2.item > brotherNode.item) {
				brotherNode = tempNode2;
			}
			tempNode = tempNode.parent;
		}

		// Go till parent - 1 to see if their brother is bigger than my brother
		// if so he becomes my brother
		System.out.println("Largest Element: " + maxNode.item);
		System.out.println("Second Largest Element: " + brotherNode.item);
		System.out.println("Comparisons: " + comparisons);
	}

	private TreeNode getBrotherNode(TreeNode node) {
		if(node.parent != null) {
			if(node.parent.left == node) {
				return node.parent.right;
			} else {
				return node.parent.left;
			}
		} else {
			return null;
		}
	}

	private void levelOrder(TreeNode root) {
		System.out.print("Level Order: ");
		if(root == null)
			return;
		LinkedList<TreeNode> parentList = new LinkedList<TreeNode>();
		LinkedList<TreeNode> currentList = new LinkedList<TreeNode>();
		parentList.add(root);
		while(!parentList.isEmpty()) {
			for(TreeNode node: parentList) {
				System.out.print(node.item + " ");
				if(node.left != null)
					currentList.add(node.left);
				if(node.right != null)
					currentList.add(node.right);
			}
			parentList = currentList;
			currentList = new LinkedList<TreeNode>();
		}
		System.out.println();
	}

	private void constructTree(int[] intarray) {
		int levels = (int) (Math.log(intarray.length)/Math.log(2));
		// Keep track of parent and child nodes
		LinkedList<TreeNode> parentList = new LinkedList<TreeNode>();
		LinkedList<TreeNode> currentList = new LinkedList<TreeNode>();
		// Start from the root node and calculate all children
		TreeNode rootNode = new TreeNode(0, null, null, null);
		parentList.add(rootNode);
		int i = 1;
		while(i <= levels) {
			// For every node at that level
			for(TreeNode node : parentList) {
				// Create a left and a right child
				TreeNode leftChild = new TreeNode(0, null, null, node);
				TreeNode rightChild = new TreeNode(0, null, null, node);
				// Point the children in the parent
				node.left = leftChild;
				node.right = rightChild;
				// Add the children to the current list
				currentList.add(leftChild);
				currentList.add(rightChild);
			}
			//Make the children the parents and try getting new children
			parentList = currentList;
			currentList = new LinkedList<TreeNode>();
			i++;
		}
		// Now parentList will contain all the nodes
		// currentList will have a junk linked list (empty)
		currentList = null;
		// The number of elements in integer array and parentList will be same
		i = 0;
		for(TreeNode node : parentList) {
			node.item = intarray[i++];
		}
		this.root = rootNode;
		parentList = null;
	}

	public SecondLargest(int[] intarray) {
		constructTree(intarray);
	}

	public static void printArray(int[] array) {
		System.out.print("Array: ");
		for(int item : array) {
			System.out.print(item + " ");
		}
		System.out.println();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		//Assume that size of array is power of 2 (greater than 1)
		int[] array = {8,9,1,2,6,4,5,0};
		//int[] array = {9,4,5,0};
		//int[] array = {6,3,1,7,9,4,5,0};
		//int[] array = {0,5};
		//int[] array = {5,0};
		//int[] array = {5,4,2,3};
		printArray(array);
		SecondLargest s = new SecondLargest(array);
		s.compute();
	}

}