Bloomberg LP Interview Question
Software DevelopersCountry: UK
Interview Type: Phone Interview
O(N) time complexity in worst case (unbalanced tree)
O(N) space complexity in worst case (unbalanced tree)
int maxDepth(Tree head){
return head == null ? 0 : Math.max(maxDepth(head.left), maxDepth(head.right)) + 1;
}
I'm wondering if this would work?
O(n) time complexity
O(1) space complexity
int maxDepth(Tree head)
{
int max=0;
if(head != NULL)
{
max = traverse(head,1);
}
return max;
}
int traverse(Tree node,int depth)
{
if(node == NULL)
return depth;
depth++;
int depthL = traverse(head->left,depth);
int depthR = traverse(head->right,depth);
return max(depthL,depthR);
}
public static int GetMaxDepth(Node root)
{
if(root == null)
return 0;
int left = GetMaxDepth(root.Left);
int right = GetMaxDepth(root.Left);
return 1 + ((left > right)?left:rigth);
}
What is meant by depth?
A number of nodes to go through til we reach a leaf node starting from the root?
Example
Nodes: {A,B,C,D,E,F,G,H} Edges: {(A,B) (A,C) (B,D) (B,E) (E,F) (E,G) (F,H)}
The depth of H is 4?
The depth of G is 3?
One idea that comes to mind is the depth first search algorithm.
Below are things that I would add to the depth first search.
1. Each time we hop to a new child node we increment a distance variable.
2. Once we have reached the end of a branch (ie a leaf or a node that has
no children) we could compare the distance variable incremented thus far
to some variable container called maximum.
If it is bigger than maximum we replace the maximum thus far with this new distance value.
3. Once we go back up a traversed branch to discover a new branch in the
tree as the algorithm would, how would we account for the new distance?
Example
Nodes:{A,B,C,D,E,F} Edges:{(A,B) (A,C) (C,D) (C,F) (D,E)}
i. we traverse to B and have our max depth as 1 so far.
ii. we go back up the tree to start back at the head and go down
the right side of the binary tree. Now the new distance should be recalculated
but how do we know it should be set to 0? In this case we are at the head so
one could set back to 0 whenever we get back up to head. But there is
a better idea and I will get to it at step iiii.
iii. We discover E and recalculate the maximum to be 3.
iiii. As we go back up the branch up to C. How do we know that the distance should be set to 1 before discovering F and incrementing it to 2?
One idea is for every hop we go DOWN the tree, we INCREMENT distance by 1 BUT every time we hop UP, we DECREMENT distance by 1.
The worst time complexity would be that of depth first search, depth first search goes through all leaves before terminating. We NEED to get to all leaves to do a fair comparison of all the potential depths to find the maximum depth.
Why do you want to complicate this problem interpreting a Binary Tree using Graph a algorithm?
Do we gain anything by doing so?
You should try being more open minded. What if the next problem was to extend the problem to a trinary tree or to solve for a b tree? I see nothing wrong with exploring different approaches to a problem.
- Vir Pratap Uttam May 04, 2015