Skip to content

Instantly share code, notes, and snippets.

@dmnugent80
Last active August 29, 2015 14:12
Show Gist options
  • Save dmnugent80/d9752d68b638f17e83a9 to your computer and use it in GitHub Desktop.
Save dmnugent80/d9752d68b638f17e83a9 to your computer and use it in GitHub Desktop.
Binary Search Tree Longest Path
/*
Interview Question:
Here's a binary tree: find the longest path within it.
So, find a path between any two leaf nodes, where the path is the longest.”
*/
public class TreeNode{
int data;
TreeNode left;
TreeNode right;
TreeNode(int d){
data = d;
left = null;
right = null;
}
}
public class BinarySearchTree{
TreeNode root;
public int getLongestPath(TreeNode root){
if (root == null){
return 0;
}
else if (root.left == null && root.right != null){
//longest path is from root
return getLongestPathHelper(root.right, 1);
}
else if (root.left != null && root.right == null){
//longest path is from root
return getLongestPathHelper(root.left, 1);
}
else{
//longest path is between deepest node on the left side and deepest node on the right side
return (getLongestPathHelper(root.left, 1) + getLongestPathHelper(root.right, 1));
}
}
public int getLongestPathHelper(TreeNode node, int level){
if (node.left == null && node.right == null){
return level;
}
else{
if (root.left == null && root.right != null){
return getLongestPathHelper(root.right, level + 1);
}
else if (root.left != null && root.right == null){
return getLongestPathHelper(root.left, level + 1);
}
else{
int left = getLongestPathHelper(root.left, level + 1);
int right = getLongestPathHelper(root.right, level + 1);
return (right > left ? right : left)
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment