CareerCup

This is on stackoverflow.com/questions/3124566/binary-tree-longest-path-between-2-nodes

int maxHeight(struct node* root)
{
     if(root == NULL)
     {
          return 0;
      }
      int lHeight = maxHeight(root->left);
      int rHeight = maxHeight(root->right);
      return (1 + (lHeight > rHeight ? lHeight : rHeight));
}

int max(int a, int b)
{
      return (a > b ? a : b);
}

int maxTreeWalk(struct node* root)
{
     if(root == NULL)
     {
          return 0;
     }
     int lHeight = maxHeight(root->left);
     int rHeight = maxHeight(root->right);

     int lDiameter = maxTreeWalk(root->left);
     int rDiameter = maxTreeWalk(root->right);

      return max(lHeight + rHeight + 1, max(lDiameter, rDiameter));
}

This is tree diameter problem and is easy :)

My approach would be:
Assign 2 variables with each node- leftLPL and rightLPL
and calculate for every node recursively:
if(node->left!=NULL)
node->leftLPL=max(node->left->leftLPL,node->left->rightLPL)+1;
else
node->leftLPL=0;
if(node->right!=NULL)
node->rightLPL=max(node->left->leftLPL,node->left->rightLPL)+1;
else
node->rightLPL=0;

same time look for the node which has max (node->leftLPL+node->rightLPL)
return that node lets say LPR;
and then...
PrintDiameterofTree(LPR)

recursively find the max path of each node ( every path will joint in one node).
int max

int check(node* n)
{
Update max;
return longest of left and right
}

Time complexity is O(n). But space is O(n^2)
anyone

recursively find the max path of each node ( every path will joint in one node).
int max

int check(node* n)
{
Update max;
return longest of left and right
}

Time complexity is O(n). But space is O(n^2)
anyone have an idea to cut down space complexity?

I think it is a tree diameter problem. You should be to find a C++ program in code.google.com/p/elements-of-programming-interviews/wiki/Programs where there is an entry called "Tree Diameter".

public class TreeCalc {

	public Result calcMaxPath(Node node) {
		if(node == null) {
			return new Result(Collections.<Integer>emptyList(), Collections.<Integer>emptyList());
		}

		Result left = calcMaxPath(node.getLeft());
		Result right = calcMaxPath(node.getRight());

		List<Integer> longestBranch = new ArrayList<Integer>();
		if(left.getLongestBranch().size() >= right.getLongestBranch().size()) {
			longestBranch.addAll(left.getLongestBranch());
		} else {
			longestBranch.addAll(right.getLongestBranch());
		}
		longestBranch.add(node.getValue());

		List<Integer> longestPath = new ArrayList<Integer>();
		longestPath.addAll(left.getLongestBranch());
		longestPath.add(node.getValue());
		Collections.reverse(right.getLongestBranch());
		longestPath.addAll(right.getLongestBranch());

		if(left.longestPath.size() > longestPath.size()) {
			longestPath = left.longestPath;
		}
		if(right.longestPath.size() > longestPath.size()) {
			longestPath = right.longestPath;
		}

		return new Result(longestBranch, longestPath);
	}

	public static class Result {
		private List<Integer> longestBranch;
		private List<Integer> longestPath;

		public Result(List<Integer> longestBranch, List<Integer> longestPath) {
			this.longestBranch = longestBranch;
			this.longestPath = longestPath;
		}

		public List<Integer> getLongestBranch() {
			return longestBranch;
		}

		public void setLongestBranch(List<Integer> longestBranch) {
			this.longestBranch = longestBranch;
		}

		public List<Integer> getLongestPath() {
			return longestPath;
		}

		public void setLongestPath(List<Integer> longestPath) {
			this.longestPath = longestPath;
		}
	}

}

any one explain the algorithm how they solved it.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class longestPath {

	class node {
		String val;

		public String getVal() {
			return val;
		}

		public void setVal(String val) {
			this.val = val;
		}

		node right;

		public node getRight() {
			return right;
		}

		public void setRight(node right) {
			this.right = right;
		}

		public node getLeft() {
			return left;
		}

		public void setLeft(node left) {
			this.left = left;
		}

		node left;

		public node(String val) {
			this.val = val;
		}

	}

	public static void main(String[] args) {

		longestPath path = new longestPath();
		path.find();

	}

	public void find() {
		node root = new node("A");
		node b = new node("B");
		node c = new node("C");
		node d = new node("D");
		node e = new node("E");
		node f = new node("F");
		node g = new node("G");
		node h = new node("H");
		node i = new node("I");
		node j = new node("J");
		node k = new node("K");
		node l = new node("L");
		node m = new node("M");
		node n = new node("N");
		root.setLeft(b);
		root.setRight(c);
		b.setLeft(d);
		b.setRight(e);
		c.setLeft(f);
		c.setRight(g);
		d.setLeft(h);
		d.setRight(i);
		i.setLeft(j);
		c.setLeft(f);
		c.setRight(g);
		f.setLeft(k);
		k.setLeft(l);
		l.setLeft(m);
		k.setRight(n);

		List<node> leftPath = findLongestPath(root.getLeft());
		for (int z = leftPath.size() - 1; z >= 0; z--) {
			System.out.println(leftPath.get(z).getVal());
		}
		System.out.println(root.getVal());
		for (node el : findLongestPath(root.getRight())) {
			System.out.println(el.getVal());
		}

	}

	private List<node> findLongestPath(node n) {
		List<node> stacks = new ArrayList<node>();
		node left = n.getLeft();
		node right = n.getRight();
		stacks.add(n);
		if (left == null && right == null) {
			return stacks;
		} else {
			List<node> sl = new ArrayList<longestPath.node>();
			List<node> sr = new ArrayList<longestPath.node>();
			if (left != null) {
				//Find longest path to left of node.
				sl = findLongestPath(left);
			}
			if (right != null) {
				//Find longest path to right of node.
				sr = findLongestPath(right);
			}
			if (sl.size() >= sr.size()) {
				for (node e : sl) {
					stacks.add(e);
				}
			} else {
				for (node e : sr) {
					stacks.add(e);
				}

			}
			return stacks;
		}
	}

}

Why not find the highest and second highest depth of the tree from root.
and the path between these two leaves will be the longest tree walk...

- let me knw if i am missing something.

int maxDepth(Node root) {
if(root == null) {
return 0;
} else {
int ldepth = maxDepth(root.left);
int rdepth = maxDepth(root.right);
return ldepth>rdepth ? ldepth+1 : rdepth+1;
}
}

int longestPath(Node root)
{
if (root == null)
return 0;

int ldepth = maxDepth(root.left);
int rdepth = maxDepth(root.right);

int lLongPath = longestPath(root.left);
int rLongPath = longestPath(root.right);

return max(ldepth + rdepth + 1, max(lLongPath, rLongPath));
}

private static int getLongestPath(NodeT root) {
int maxPath[] = new int[1];
getLongestPath(root,maxPath);
return maxPath[0];
}

private static int getLongestPath(NodeT root, int[] maxPath) {
if(root == null)
return 0;
else{
int lH = getLongestPath(root.left,maxPath);
int rH = getLongestPath(root.right,maxPath);
if(maxPath[0]<lH+rH+1){
maxPath[0] = lH+rH+1;
}
return 1 + Math.max(lH, rH);
}
}

int LongestPath(struct BinaryTreeNode *root,int *ptr)
{
int left,right;
if(!root)
return 0;
left = LongestPath(root->left , ptr);
right = LongestPath(root->right , ptr);
if(left+right > *ptr)
*ptr = left+right;
if(left>right)
return left +1;
else
return right + 1;
}

1
/ \
2 3
/ \
4 5
/ \ \
6 7 8
/ \ \
9 a b

At any given node :
path len with current node as root = max pathlen with node->left as root (L) + max pathlen with node->right as root (R) + 1

At each recursion function will return the maximum length possible with that node, whcih is either 1+ max(left) or 1 + max(right),
Also it will update the max length if the current path length is more that current max.

int maxlen;
  len = maxpath(root,maxlen);
  cout << maxlen;
  
  
  int maxpath(node *root, int &maxlen) {
      if (root==NULL) {
          return 0;
      }
      int l = maxpath(root->left,maxlen);
      int r = maxpath(root->right,maxlen);
      int curmax = 1 + l + r;
      if (curmax > maxlen) maxlen = curlen;
      return max(1+l, 1+r);
  }