# How to find longest path of a given binary tree?

2,081 views
How to find longest path of a given binary tree?
posted Oct 28, 2013

+1 vote

Considering the Tree as binary

``````         a
/\
b  c
/    / \
d    e   f
/ \        \
g   h        p
\
k
``````

The longest leaf to leaf path would be k-h-d-b-a-c-f-p i.e of length 8.

1. Calculate the diameter at each node (assuming node as a root of the tree)
2. Diameter is the height of left subtree + height of right subtree + 1.
3. Pick the highest diameter amongst all.
Check this if this works...
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));
}
Similar Questions
``````      40
/\
20 60
/\  \
10 30  80
/   /\
25  70 90
\
75

longest path
25 30 20 40 60 80 70 75
25 ----> 75
``````