Yahoo Interview Question
Software Engineer / DevelopersWud like to make one point: whether its above recursive approach or bfs or dfs to find the depth of tree, it all run in O(n) time complexity, where n is the number of nodes in tree, as each node is required to be visited before answering the depth of tree.
About memory consumption, it varies based on the type of tree. If tree has more depth than breadth, dfs will consume more memory otherwise bfs will consume more memory.
Since we require to optimize memory used , so I think iterative solution would be better than recursive.
Iterative approach:-
Solution is similar to iterative level-order-traversal of a tree using a queue .
For each level increment the counter.
Final value of the counter would be the required answer
int FindDepth(Node *node)
- dronzer709 June 21, 2011{
int leftDepth, rightDepth;
if (node == NULL)
return 0;
else{
leftDepth = FindDepth(node->left);
rightDepth = FindDepth(node->right);
if (leftDepth > rightDepth)
return (leftDepth+1);
else
return (rightDepth+1);
}
}