Work in HR? Unlock Free Profile Intern Interview Question

"Find maximum depth of a tree."
Add Tags [?]

Part of a Intern Interview Review - one of 4,656 Interview Reviews

Answers & Comments

of 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;

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

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

Tags are like keywords that help categorize interview questions that have something in common.