CareerCup

//				5
//		3				9
//1					6		10

class Response
{
	public Response(int c, Node l)
	{
		count=c;
		last=l;
	}
	int count;
	Node last;
}
class Node
{
	public Node(int n)
	{
		value=n;
	}
	int value;
	Node right;
	Node left;
}
public class LongestPath
{
	static int max = 0;
	static Node[] r;
	
	static Response getLongestPath(Node root)
	{
		Response left=null, right=null;
		
		if(root.left == null && root.right==null)
			return new Response(1,root);
		
		if(root.left != null)
			left = getLongestPath(root.left);
		if(root.right != null)
			right = getLongestPath(root.right);
		
		if(root.left==null)
			return new Response(right.count+1, right.last);
		if(root.right==null)
			return new Response(left.count+1, left.last);
		
		if(left.count + right.count + 1 > max)
		{
			max = left.count + right.count +1;
			r[0] = left.last;
			r[1] = right.last;
		}
		if(left.count > right.count)
			return new Response(left.count+1, left.last);
			
		return new Response(right.count+1, right.last);
	}
	public static void main(String... args)
	{
		Node root = new Node(5);
		root.left = new Node(3);
		root.left.left = new Node(1);
		root.right = new Node(9);
		root.right.left = new Node(6);
		root.right.right = new Node(10);
		
		r=new Node[2];
		Response temp = getLongestPath(root);
		System.out.println(r[0].value +" "+ r[1].value);
	}
}

Consider a particular "node":- we have three cases
1. Longest Possible path includes node->left and not this node
2. Longest Possible path includes node->right and not his node
3. Longest Possible path includes this "node"

Thus, longest possible path should be maximum of these three: (node->left, node->right, 1+height(node->left) + height(node->right))

Do a BFS from a randomly chosen node, and find the farthest leaf. Then do the BFS from that farthest node to find the farthest node again. This two nodes are the answer :)

int FindDia(NODE root,int *length , int *NullNodeValue , int *LeftNullNode , int *RightNullNode)
{
int a,b;
int left, right;
if(root == NULL)
return 0;
a=FindDia(root->left,length,&left,LeftNullNode,RightNullNode);
b=FindDia(root->right,length,&right,LeftNullNode,RightNullNode);
if(!a && !b)
{
*NullNodeValue = root->data;
if(!(*length))
*length =1;
return 1;
}
if(a+b+1>*length)
{
*length = a+b+1;
*LeftNullNode = left;
*RightNullNode = right;
}
if(a>b)
{
*NullNodeValue = left;
return a+1;
}
else
{
*NullNodeValue = right;
return b+1;
}
}int FindDia(NODE root,int *length , int *NullNodeValue , int *LeftNullNode , int *RightNullNode)
{
int a,b;
int left, right;
if(root == NULL)
return 0;
a=FindDia(root->left,length,&left,LeftNullNode,RightNullNode);
b=FindDia(root->right,length,&right,LeftNullNode,RightNullNode);
if(!a && !b)
{
*NullNodeValue = root->data;
if(!(*length))
*length =1;
return 1;
}
if(a+b+1>*length)
{
*length = a+b+1;
*LeftNullNode = left;
*RightNullNode = right;
}
if(a>b)
{
*NullNodeValue = left;
return a+1;
}
else
{
*NullNodeValue = right;
return b+1;
}
}

1) Brute force method: O(n^2), n is the number of nodes. Take each node as root, we find the longest path starting from it. This can be done in O(n) using DFS or BFS. Then, we take the longest one of the longest paths starting from each node.

2) Dynamic Programming: O(n). The idea metioned above is extended to a general tree and more details are added. Take a random node as root (e.g., 0), the longest path either passes this node or not. If the longest path does not pass this node, then it must come from one of the subtrees (can be more than two). Otherwise, the longest path must pass the root and it can be divided into three parts, i.e., path from a subtree root to leave, root, path from another subtree root to leave. Then, the length of the longest path should be length(longestSubrootToLeavePath) + 1 + length(secondLongestSubrootToLeavePath) + 1.
The root to leave path is deinfed as the path from the root to the leave. Subroot is the root of one of the subtrees. Therefore, we need to find three paths for a tree, the longest path, longest path from a subtree root to a leave, the second longest path from a sub tree root a leave. Two subtrees are different otherwise the composed path from them will not pass the root. Then longest path with a tree = max(longest path passing root, longest paths in subtrees).

3) Take a random node (a), find the farthest node (b) from the node a. Then find the farthest node (c) from the node (b). Why is it correct? Think node a as the root, the node b must a leave (otherwise the leaves in this subtree must have longer paths). If the longest path passes the root, then the longest path can be divided into three parts, path1 + root + path2. It is easy to understand that path1 or path2 has to starts with node b and path2 should be the second longest path from the root. At the same time, the other end of the second longest path is the farthest node from node b. If the longest path does not pass the root, then the longest path in the subtree T (root d) of a where node b resdies. More importantly, b is still the farthest node from the root d. Therefore, we can proceed the same reasoning as above.

import java.util.*;

public class LongestPathInTree {
   //tree is represented as an adjacent list
   private List<List<Integer>> adjacentList;
   private Path longestPath;
   //is a node visited?
   private boolean[] visited;

   public LongestPathInTree (List<List<Integer>> adjacentList) {
       this.adjacentList = adjacentList;
       this.visited = new boolean[adjacentList.size()];
   } 

   public Path getLongestPath() {
       return longestPath;
   }

   //traverse paths between every pair of nodes
   public void bruteForceMethod() {
       //default path is shortest
       longestPath = new Path();
       for(int i = 0; i < adjacentList.size(); i++) {
           Arrays.fill(visited,false);
           depthFirstSearchPath(i,i,0);
       }
   }

   public void depthFirstSearchPath(int treeRoot, int subTreeRoot, int pathLength) {
         List<Integer> neighbors = adjacentList.get(subTreeRoot);
	 //in fact, only leave nodes need checking but it does not harm to check every node
	 if(pathLength > longestPath.getLength()) {
	     longestPath.setStart(treeRoot);
	     longestPath.setEnd(subTreeRoot);
	     longestPath.setLength(pathLength);
	 }
	 for(int u : neighbors) {
	     if(!visited[u]) {
		 visited[u] = true;
		 depthFirstSearchPath(treeRoot, u, pathLength+1);
	     }
	 }
   }

   public void dpMethod() {
       Arrays.fill(visited,false);
       int root = 0;
       longestPath = findLongestPath(root)[0];
   }

   public Path[] findLongestPath(int root) {
       visited[root] = true;
       //longest path in subtrees (don't have to pass the subtree root)
       Path longestPathInSubtrees = null;
       //longest path from a subtree root  to a leave
       Path longestPathFromSubrootToSubLeave = null;
       //second longest path from another subtree root to a leave
       //the two subtrees must be different
       Path secondLongestPathFromSubrootToSubLeave = null;
       List<Integer> neighbors = adjacentList.get(root);
       //System.out.println(neighbors);
       for(int u : neighbors) {
           if(!visited[u]) {
	       //path[0] is the longest path in a subtree
	       //path[1] is the longest path from the subtree root to a leave
	       Path[] paths = findLongestPath(u);
	       if(longestPathInSubtrees == null
	           || longestPathInSubtrees.getLength() < paths[0].getLength()) {
	           longestPathInSubtrees = paths[0];
	       }
	       if(longestPathFromSubrootToSubLeave == null
		     || longestPathFromSubrootToSubLeave.getLength() < paths[1].getLength()) {
		   secondLongestPathFromSubrootToSubLeave = longestPathFromSubrootToSubLeave;
		   longestPathFromSubrootToSubLeave = paths[1];
	       } else if(secondLongestPathFromSubrootToSubLeave == null
		     || secondLongestPathFromSubrootToSubLeave.getLength() < paths[0].getLength() ) {
		   secondLongestPathFromSubrootToSubLeave = paths[1];
	       }
	   }
       }
       //System.out.println("Root: " + root);
       //System.out.println(longestPathFromSubrootToSubLeave);
       //System.out.println(secondLongestPathFromSubrootToSubLeave);
       if (longestPathFromSubrootToSubLeave == null
            && secondLongestPathFromSubrootToSubLeave == null) {
	    //leave
           return new Path[] {new Path(root, root, 0), new Path(root, root, 0)};
       }else {
	   //the potential longest path passing root
	   Path path = null;
	   //this node might only have one subtree
	   if(secondLongestPathFromSubrootToSubLeave == null) {
	       path = new Path(longestPathFromSubrootToSubLeave.getEnd(),
	                    root, longestPathFromSubrootToSubLeave.getLength()+1);
	   }else {
	       path = new Path(longestPathFromSubrootToSubLeave.getEnd(),
			    secondLongestPathFromSubrootToSubLeave.getEnd(),
			    longestPathFromSubrootToSubLeave.getLength() + 1
			    + secondLongestPathFromSubrootToSubLeave.getLength() + 1);
	   }
	   Path[] paths = new Path[2];
	   //the longest path in the tree
	   paths[0] = path.getLength() > longestPathInSubtrees.getLength() ? path : longestPathInSubtrees;
	   //the longest path from the root to a leave
	   paths[1] = new Path(root, longestPathFromSubrootToSubLeave.getEnd(),
				    longestPathFromSubrootToSubLeave.getLength()+1);
	   return paths;
       }
   }

   public void farthestFarthestMethod() {
       longestPath = new Path();
       int root = 0;
       Arrays.fill(visited,false);
       depthFirstSearchPath(root, root, 0);
       Arrays.fill(visited,false);
       root = longestPath.getEnd();
       Arrays.fill(visited, false);
       depthFirstSearchPath(root, root, 0);
   }

   public static void main(String[] args) {
       List<List<Integer>> tree = new ArrayList<List<Integer>>();
       List<Integer> ls0 = new ArrayList<Integer>();
       ls0.add(1);
       ls0.add(2);
       ls0.add(3);
       tree.add(ls0);
       List<Integer> ls1 = new ArrayList<Integer>();
       ls1.add(0);
       ls1.add(4);
       ls1.add(5);
       tree.add(ls1);
       List<Integer> ls2 = new ArrayList<Integer>();
       ls2.add(0);
       ls2.add(6);
       tree.add(ls2);
       List<Integer> ls3 = new ArrayList<Integer>();
       ls3.add(0);
       tree.add(ls3);
       List<Integer> ls4 = new ArrayList<Integer>();
       ls4.add(1);
       ls4.add(7);
       tree.add(ls4);
       List<Integer> ls5 = new ArrayList<Integer>();
       ls5.add(1);
       ls5.add(9);
       tree.add(ls5);
       List<Integer> ls6 = new ArrayList<Integer>();
       ls6.add(2);
       ls6.add(8);
       tree.add(ls6);
       List<Integer> ls7 = new ArrayList<Integer>();
       ls7.add(4);
       ls7.add(13);
       tree.add(ls7);
       List<Integer> ls8 = new ArrayList<Integer>();
       ls8.add(6);
       tree.add(ls8);
       List<Integer> ls9 = new ArrayList<Integer>();
       ls9.add(5);
       ls9.add(10);
       tree.add(ls9);
       List<Integer> ls10 = new ArrayList<Integer>();
       ls10.add(9);
       ls10.add(11);
       tree.add(ls10);
       List<Integer> ls11 = new ArrayList<Integer>();
       ls11.add(10);
       ls11.add(12);
       tree.add(ls11);
       List<Integer> ls12 = new ArrayList<Integer>();
       ls12.add(11);
       tree.add(ls12);
       List<Integer> ls13 = new ArrayList<Integer>();
       ls13.add(7);
       ls13.add(14);
       tree.add(ls13);
       List<Integer> ls14 = new ArrayList<Integer>();
       ls14.add(13);
       ls14.add(15);
       tree.add(ls14);
       List<Integer> ls15 = new ArrayList<Integer>();
       ls15.add(14);
       tree.add(ls15);
       LongestPathInTree finder = new LongestPathInTree(tree);
       finder.bruteForceMethod();
       System.out.println(finder.getLongestPath());
       finder.dpMethod();
       System.out.println(finder.getLongestPath());
       finder.farthestFarthestMethod();
       System.out.println(finder.getLongestPath());
   }
}

class Path {
    private int start;
    private int end;
    private int length;

    public Path() {
        this.start = Integer.MIN_VALUE;
	this.end = Integer.MIN_VALUE;
	this.length = Integer.MIN_VALUE;
    }

    public Path(int start, int end, int length) {
        this.start = start;
	this.end = end;
	this.length = length;
    }

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }

    public int getLength() {
        return length;
    }

    public void setStart(int start) {
        this.start = start;
    }

    public void setEnd(int end) {
        this.end = end;
    }

    public void setLength(int length) {
        this.length = length;
    }

    public String toString() {
        return "start: " + start + " end: " + end + " length: " + length;
    }

}

Longest possible path in the tree = (reverse of longest path from root in left sub tree) + root+ (longest possible path from root in right sub tree)

package trees;

/**
 * Program prints the longest possible path starting at the root in a tree
 * followed by the longest possible path which can start at any node in the tree
 * Longest path in the tree = reverse(longest path from root in the left sub
 * tree) + root + (longest path from root in the right sub tree)
 * 
 * 
 * @author sriniatiisc
 * 
 */

public class LongestPossiblePathInTree {

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);

		root.appendLeft(2).appendLeft(4);
		root.getLeft().appendRight(5).appendLeft(8);

		root.appendRight(3).appendLeft(6);
		root.getRight().appendRight(7);

		TreeNode.print(root);

		String longestPath = longestPath(root);
		System.out
				.println("Longest path starting at root node: " + longestPath);

		String longestLPath = longestPath(root.getLeft());
		String longestRPath = longestPath(root.getRight());

		System.out.println("Longest path in the tree: " + reverse(longestLPath)
				+ root.getData() + longestRPath);

	}

	private static String longestPath(TreeNode root) {
		if (root == null)
			return "";

		String lPath = longestPath(root.getLeft());
		String rPath = longestPath(root.getRight());

		if (lPath.length() >= rPath.length()) {
			return root.getData() + lPath;
		} else {
			return root.getData() + rPath;
		}
	}

	public static String reverse(String s) {
		char[] str = s.toCharArray();

		int i = 0;
		int j = str.length - 1;

		while (i <= j) {
			char t = str[i];
			str[i] = str[j];
			str[j] = t;
			i++;
			j--;
		}
		return new String(str);
	}
}

public int maxHeight(BinaryTree b)
{
if(b==null) return 0;
return 1 + Math.max(maxHeight(b.left), maxHeight(b.right));
}

public void maxPath(BinaryTree b,int[] a,int index)
{
if(b==null)
{
for(int i = 0; i < index;i++)
System.out.println(a[i] + "");
return;
}
a[index] = b.data;
index++;
if(maxHeight(b.left) > maxHeight(b.right))
maxPath(b.left, a, index);
else maxPath(b.right, a, index);

}

Here is a pseudo code that runs with O(n) memory and O(n) time complexity. Conceptually it’s a breadth-first-traversal with queue.
I’ve used an additional queue to hold the leafs for final answer.

Algorithm -Starts
Node marker <-- create a node object  // this acts as delimiter of each levels nodes 
Q1 <- initialize an empty queue
Q2 <- initialize an empty queue 

//For each node removed from Q1 its children are stored again in Q1. If the removed
//node doesn’t have any children then only it will be queued to Q2.
//The loop exits when Q1 is empty and at that time all nodes in Q2 are the leafs of all longest paths from root.

Q1.enqueue(root);
Q1.enqueue(marker);

While true 
	Node n=Q1.dequeue();
	If n is marker
		If Q1 is empty
			Break;
		Else
			Q1.enqueue(n);
			Q2.removeAll();
			continue
		End-if
	End-if

	boolean hasChildren=false;
	if n has left child
		Q1.enqueue(n->leftChild);
		hasChildren=true;
	end-if
if n has right child
		Q1.enqueue(n->rightChild);
		hasChildren=true;
	end-if
	if hasChildren == false
		Q2.enqueue (n);
	End-if
End-while

//all nodes in Q2 are the answer
Algorithm –Ends

ArrayList<Node> leafNodes = new ArrayList<Node>(); // Required Anser
CALL : longPathNodes(root, leafNodes);

Function:

int longPathNodes(Node node, ArrayList<Node> leafNodes){

if(node == null){
    return 0;
}

ArrayList<Node> leftNodes = new ArrayList<Node>(0);
ArrayList<Node> rightNodes = new ArrayList<Node>(0);

int leftSize = longPathNodes(node.left, leftNodes);
int rightSize = longPathNodes(node.right, rightNodes);

if(leftSize == rightSize){
      leafNodes.addAll(leftNodes);
      leafNodes.addAll(rightNodes);
}else if (leftSize > rightSize){
      leafNodes.addAll(leftNodes);
} else {
     leafNodes.addAll(rightNodes);
}

if(leftSize == 0 &&  rightSize==0){
    leafNodes.add(node);
}

return Math.max(leftSize, rightSize)+1;

}

def findFarthestLeaf(root,level,maxLevel,leaf):
    if root==None:
        return 0,None
    if root.left==None and root.right==None:
        if level>=maxLevel:
            return level,root
        else:
            return maxLevel,leaf

    if root.left!=None:
        level,leaf = findFarthestLeaf(root.left,level+1,maxLevel,leaf)
    if root.right!=None:
        level,leaf = findFarthestLeaf(root.right,level+1,maxLevel,leaf)

    return level,leaf

findFarthestLeaf(root,0,0,None)