Today’s question is going to be a quick one. We want to find longest path in tree. What does Path mean in a Tree context?
The Tree wikipedia page and Tree/Graph Theory shed some light.
Longest Path is the longest path from any two nodes in a tree.
Diameter is the longest path from any two nodes in a tree/graph.
Hence it seems like we want to find longest path in tree, which is also called diameter of the tree.
Below is my code which takes time-complexity O(n) thanks to computing height and diameter at the same time.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
/* * @Author: Ajk Palikuqi * http://en.wikipedia.org/wiki/Tree_(graph_theory) * @Question: How to find longest path in tree * */ package iqLib.treeLib; public class LongestPath { public static int findLongestPath(TreeNode root) { // longest path = max (h1 + h2 + 2, longestpath(left), longestpath(right); int[] treeInfo = longestPathHelper(root); return treeInfo[0]; } private static int[] longestPathHelper(TreeNode root) { int[] retVal = new int[2]; if (root == null) { //height and longest path are 0 retVal[0] = 0; retVal[1] = 0; } int[] leftInfo = longestPathHelper(root.getLeft()); int[] rightInfo = longestPathHelper(root.getRight()); retVal[0] = Math.max(leftInfo[1] + rightInfo[1] + 2, Math.max(leftInfo[0], rightInfo[0])); retVal[1] = Math.max(leftInfo[1], rightInfo[1]) + 1; return retVal; } } |
Well in the comfort of my home, I came up with this code in 5 mins.
Hope you guys enjoyed it… and I’ll see you guys next time!
The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017