Amazon.com

  www.amazon.com
  www.amazon.com

Interview Question

Intern Interview

Find maximum depth of a tree.

Answer

Interview Answer

1 Answer

0

Suppose you have a tree with a Node class that has 2 pointers of type node, one left and the other right. Suppose further we have variable root of type Node * that points to the Node at the top of the tree. Let all invalid left/right pointers equal nullptr (or 0). The following is the answer:

unsigned depth(Node *parent)
{
    if(parent == nullptr)
        return 0;

    return max(depth(parent->left), depth(parent->right)) + 1;
}

Notes:
1.) max is from #include<algorithm>.
2.) Test a node of height zero (starting call with nullptr). It equals zero as intended.
3.) Test a tree with a single node: max(0,0) + 1 = 1 as intended.
4.) It seems to work for any other size as long as there is no stack overflow.
5.) If the tree is not binary, simply replace the second return statement with a for loop to loop through all children, keeping track of the maximum depth returned by all of them. Then, add one to that.

bigballscode on Oct 7, 2013

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up