Last active
August 29, 2015 14:12
-
-
Save dmnugent80/d9752d68b638f17e83a9 to your computer and use it in GitHub Desktop.
Binary Search Tree Longest Path
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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