Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
#include <iostream>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
left_ = right_ = NULL;
}
int val_;
Node *left_, *right_;
};
int Height(Node *n, int &max_distance)
{
int height = 0;
if (n) {
int l = Height(n->left_, max_distance);
int r = Height(n->right_, max_distance);
height = 1 + max(l, r);
max_distance = max(max_distance, 1 + l + r);
}
return height;
}
int main()
{
/*
(1)
/
(2)
/ \
(3) (4)
/ /
(6) (7)
/ \
(5) (8)
*/
Node n1(1);
Node n2(2);
Node n3(3);
Node n4(4);
Node n5(5);
Node n6(6);
Node n7(7);
Node n8(8);
n1.left_ = &n2;
n2.left_ = &n3;
n2.right_ = &n4;
n3.left_ = &n6;
n4.left_ = &n7;
n7.left_ = &n5;
n7.right_ = &n8;
int max_distance = 0;
Height(&n1, max_distance);
cout << max_distance << "\n";
return 0;
}
Correcting the approach -
public static void main(String[] args){
BT N12 = new BT(12, null, null);
BT N11 = new BT(11, N12, null);
BT N10 = new BT(10, null, N11);
BT N9 = new BT(9, N10, null);
BT N8 = new BT(8, null, null);
BT N6 = new BT(6, null, null);
BT N5 = new BT(5, null, null);
BT N7 = new BT(7, N5, N8);
BT N4 = new BT(4, N7, null);
BT N3 = new BT(3, N6, null);
BT N2 = new BT(2, N3, N4);
BT N1 = new BT(1, N2, N9);
int[] maxdist = new int[1];
maxdist[0] = Integer.MIN_VALUE;
depth(N1, -1, maxdist);
System.out.println(maxdist[0]+1);
}
public static int depth(BT node, int dist, int[] maxdist){
if(node == null)
if(dist == -1)
return 0;
else {
maxdist[0] = Math.max(maxdist[0], dist);
return dist-1;
}
dist = depth(node.left, dist==-1?-1:dist+1, maxdist);
dist = depth(node.right, dist==-1?-1:dist+1, maxdist);
return dist;
}
static class BT{
int val;
BT left;
BT right;
public BT(int val, BT left, BT right){
this.val = val;
this.left = left;
this.right = right;
}
}
Let me know if the following code works fine with all inputs,
tested few inputs and worked for me not sure if I missed any case..
typedef struct node tNode;
struct node
{
tNode *left;
tNode *right;
int data;
};
int maxdistancebtwnodes(tNode* node, int *dist)
{
if(node == NULL)
{
*dist = 0;
return -1;
}
int lefth=0, righth=0, ldist=*dist, rdist=*dist;
lefth = maxdistancebtwnodes(node->left, &ldist) +1;
righth = maxdistancebtwnodes(node->right, &rdist) +1;
*dist = (ldist>rdist)?ldist:rdist;
if(lefth+righth+1 > *dist)
*dist = lefth+righth+1;
return ((lefth > righth)? lefth: righth);
}
int main()
{
tNode *root;
createyourtree(&root);
int maxdist=0;
maxdistancebtwnodes(root, &maxdist);
}
public static void maxDistanceAnyTwo(BinaryTree.Node root) {
if (root == null) {
return;
}
Result r = new Result();
maxDistanceAnyTwo(root, r);
System.out.println("MaxDistance : " + r.maxDistance);
}
public static int maxDistanceAnyTwo(BinaryTree.Node root, Result r) {
if (root == null) {
return 0;
}
int left = maxDistanceAnyTwo(root.left, r);
int right = maxDistanceAnyTwo(root.right, r);
int maxAtThisNode = left + right;
if (maxAtThisNode > r.maxDistance) {
r.maxDistance = maxAtThisNode;
}
return 1 + Math.max(left, right);
}
public static class Result {
int maxDistance;
}
check from bottom up recursively.
for every node, it has a longest left subtree length lmax, and right subtree length rmax
update result if lmax + rmax > result
and return max(lmax, rmax) to its parent node.
note: the idea behind it is that it's not necessarily the root node be included in the longest path.
int maxPath = 0;
public static int largestDistanceBST(TreeNode root){
searchHelper(root);
return maxPath-1;
}
public static int searchHelper(TreeNode root){
if(root==null){
return 0;
}
int leftPath = searchHelper(root.left);
int rightPath = searchHelper(root.right);
maxPath = Math.max(maxPath,leftPath+1+rightPath);
return leftPath+rightPath+1;
}
public static void main(String[] args){
BT N9 = new BT(9, null, null);
BT N8 = new BT(8, null, null);
BT N7 = new BT(7, null, null);
BT N6 = new BT(6, null, null);
BT N5 = new BT(5, null, null);
BT N4 = new BT(4, N8, N9);
BT N3 = new BT(3, N6, N7);
BT N2 = new BT(2, N4, N5);
BT N1 = new BT(1, N2, N3);
System.out.println(dia(N1));
}
public static int dia(BT root){
return depth(root.left) + depth(root.right)+1;
}
public static int depth(BT node){
if(node == null)
return 0;
int lh = depth(node.left)+1;
int rh = depth(node.right)+1;
return Math.max(lh, rh);
}
static class BT{
int val;
BT left;
BT right;
public BT(int val, BT left, BT right){
this.val = val;
this.left = left;
this.right = right;
}
}
Finds longest path of a tree. The longest path may not be through the root.
Used custom object TResult.
Time complexity : O(n)
Kindly suggest for any improvement in the code.
- iLoveCoding85 October 21, 2017