CareerCup

Finds longest path of a tree. The longest path may not be through the root.
Used custom object TResult.

Time complexity : O(n)
Kindly suggest for any improvement in the code.

public class TreePath {

	public static void main(String args[]) {
		
		/*
		 *                   15
		 *                  /  \
		 * 				   15  20
		 * 				  /  \
		 *     			 3    7
		 *     				 /
		 *     				8
		 *     			   /
		 *     			  9
		 * 	
		 */

		Node tree = new Node(10);
		tree.left = new Node(15);
		tree.right = new Node(20);

		tree.left.left = new Node(3);
		tree.left.right = new Node(7);

		tree.left.right.left = new Node(8);
		tree.left.right.left.left = new Node(9);

		TResult res = findLongestPath(tree);

		System.out.println(res.overallMaxPathLength);

	}

	/**
	 * Wrapper for Recursion method 
	 * Increment the path value by 1 for root
	 * 
	 * @param tree
	 * @return
	 */
	private static TResult findLongestPath(Node tree) {
		TResult res = null;
		if (tree != null) {
			res = findLongestPathRec(tree);
			// Adding one for the root node
			res.overallMaxPathLength++;
		}
		return res;
	}

	private static TResult findLongestPathRec(Node node) {
		if (node == null) {
			return new TResult(0, 0);
		}

		TResult lRes = findLongestPathRec(node.left);
		TResult rRes = findLongestPathRec(node.right);

		int maxPathOnSingleSide = Math.max(lRes.maxPathOnSingleSide, rRes.maxPathOnSingleSide);
		int overallMaxLongPath = Math.max(Math.max(lRes.overallMaxPathLength, rRes.overallMaxPathLength),
				lRes.maxPathOnSingleSide + rRes.maxPathOnSingleSide);

		return new TResult(maxPathOnSingleSide + 1, overallMaxLongPath);
	}

}

/*
 * Result Object hold overall long path
 */
class TResult {
	int overallMaxPathLength;
	int maxPathOnSingleSide;

	TResult(int i, int j) {
		maxPathOnSingleSide = i;
		overallMaxPathLength = j;
	}
}

/**
 * 
 * Tree Node
 *
 */
class Node {
	int data;
	Node left;
	Node right;

	Node(int data) {
		this.data = data;
		left = right = null;
	}
}

#include <iostream>

using namespace std;

class Node {
	public:
		Node(int val)
		{
			val_ = val;
			left_ = right_ = NULL;
		}
		int val_;
		Node *left_, *right_;
};

int Height(Node *n, int &max_distance)
{
	int height = 0;
	if (n) {
		int l = Height(n->left_, max_distance);
		int r = Height(n->right_, max_distance);
		height = 1 + max(l, r);
		max_distance = max(max_distance, 1 + l + r);
	}
	return height;
}

int main()
{
/*
       (1)
       /
    (2)
    / \
  (3) (4) 
  /   /
(6)	(7)
    / \
  (5) (8)
*/
	Node n1(1);
	Node n2(2);
	Node n3(3);
	Node n4(4);
	Node n5(5);
	Node n6(6);
	Node n7(7);
	Node n8(8);
	n1.left_ = &n2;
	n2.left_ = &n3;
	n2.right_ = &n4;
	n3.left_ = &n6;
	n4.left_ = &n7;
	n7.left_ = &n5;
	n7.right_ = &n8;

	int max_distance = 0;
	Height(&n1, max_distance);
	cout << max_distance << "\n";

	return 0;
}

@sudip.innovates. It's not necessary that the longest path goes through the root node. I.e. the root node may be not in the longest path.

this is the same as finding the diameter of the tree

@Alex - Can you please explain the scenario, when the longest path would not include the root?

Wouldn't this be:

1. Distance b/w the left most and right most nodes if root has a right and left nodes.
2. Distance b/w the leftmost and rightmost nodes of the node in the next level if 1. is false.

?

@Alex - Got it.. Thanks for correcting :)

Correcting the approach -

public static void main(String[] args){
    BT N12 = new BT(12, null, null);
    BT N11 = new BT(11, N12, null);
    BT N10 = new BT(10, null, N11);
    BT N9 = new BT(9, N10, null);
    
    BT N8 = new BT(8, null, null);
    BT N6 = new BT(6, null, null);
    BT N5 = new BT(5, null, null);
    BT N7 = new BT(7, N5, N8);
    BT N4 = new BT(4, N7, null);
    BT N3 = new BT(3, N6, null);
    BT N2 = new BT(2, N3, N4);
    BT N1 = new BT(1, N2, N9);
    
    int[] maxdist = new int[1];
    maxdist[0] = Integer.MIN_VALUE;
    depth(N1, -1, maxdist);
    System.out.println(maxdist[0]+1);
  }
  
    
  public static int depth(BT node, int dist, int[] maxdist){
  	if(node == null)
      if(dist == -1)
      	return 0;
      else {
      	maxdist[0] = Math.max(maxdist[0], dist);
      	return dist-1;
      }
    
    dist = depth(node.left, dist==-1?-1:dist+1, maxdist);
    dist = depth(node.right, dist==-1?-1:dist+1, maxdist);
    return dist;
  }
  
  
  static class BT{
  	int val;
    BT left;
    BT right;
    
    public BT(int val, BT left, BT right){
      this.val = val;
      this.left = left;
      this.right = right;
    }
    
  }

Let me know if the following code works fine with all inputs,
tested few inputs and worked for me not sure if I missed any case..

typedef struct node tNode;

struct node
{
	tNode *left;
	tNode *right;
	int data; 
};

int maxdistancebtwnodes(tNode* node, int *dist)
{
	if(node == NULL)
	{
		*dist = 0;
		return -1;
	}

	int lefth=0, righth=0, ldist=*dist, rdist=*dist;

	lefth = maxdistancebtwnodes(node->left, &ldist) +1;
	righth = maxdistancebtwnodes(node->right, &rdist) +1;
	
	*dist = (ldist>rdist)?ldist:rdist;
	
	if(lefth+righth+1 > *dist)
			*dist = lefth+righth+1;

	return ((lefth > righth)? lefth: righth);
}

int main()
{
	tNode *root;
	createyourtree(&root);

	int maxdist=0;

	maxdistancebtwnodes(root, &maxdist);

}

public static void maxDistanceAnyTwo(BinaryTree.Node root) {
        if (root == null) {
            return;
        }

        Result r = new Result();
        maxDistanceAnyTwo(root, r);

        System.out.println("MaxDistance : " + r.maxDistance);
    }


    public static int maxDistanceAnyTwo(BinaryTree.Node root, Result r) {
        if (root == null) {
            return 0;
        }

        int left = maxDistanceAnyTwo(root.left, r);
        int right = maxDistanceAnyTwo(root.right, r);

        int maxAtThisNode = left + right;
        if (maxAtThisNode > r.maxDistance) {
            r.maxDistance = maxAtThisNode;
        }

        return 1 + Math.max(left, right);
    }

    public static class Result {
        int maxDistance;
    }

check from bottom up recursively.
for every node, it has a longest left subtree length lmax, and right subtree length rmax
update result if lmax + rmax > result
and return max(lmax, rmax) to its parent node.

note: the idea behind it is that it's not necessarily the root node be included in the longest path.

int maxPath = 0;
    public static int largestDistanceBST(TreeNode root){
        searchHelper(root);
        return maxPath-1;
    }
    
    public static int searchHelper(TreeNode root){
        if(root==null){
            return 0;
        }
        
        int leftPath = searchHelper(root.left);
        int rightPath = searchHelper(root.right);
        maxPath = Math.max(maxPath,leftPath+1+rightPath);
        return leftPath+rightPath+1;
    }

public static void main(String[] args){
    BT N9 = new BT(9, null, null);
    BT N8 = new BT(8, null, null);
    BT N7 = new BT(7, null, null);
    BT N6 = new BT(6, null, null);
    BT N5 = new BT(5, null, null);
    BT N4 = new BT(4, N8, N9);
    BT N3 = new BT(3, N6, N7);
    BT N2 = new BT(2, N4, N5);
    BT N1 = new BT(1, N2, N3);
    
    System.out.println(dia(N1));
    
  }
  
  public static int dia(BT root){
  	return depth(root.left) + depth(root.right)+1;
  }
  
  public static int depth(BT node){
  	if(node == null)
      return 0;
    
    int lh = depth(node.left)+1;
    int rh = depth(node.right)+1;
    return Math.max(lh, rh); 
  }
  
  
  static class BT{
  	int val;
    BT left;
    BT right;
    
    public BT(int val, BT left, BT right){
      this.val = val;
      this.left = left;
      this.right = right;
    }
    
  }

en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm