Job interview question made harder, check all except root?

  algorithm, c++, tree

I was given this problem in an interview, while it seemed really easy at first when I got deeper it neraly sound impossible to me with tons of edge cases.

requirments:

Imagine a tree where each node can have from 0 to 10 children, each child has its own weight, write a function that does the following:

  1. In case the root has no children return -1;
  2. else, return the sum of the weights of all children of the tree (except the root itself).

I tried something like:

int my_func(node *root) {
    if (root->isleaf())
    {
        return -1;
    }
    int result = 0;
    for (int i = 0; i < root->num_of_children(); ++i)
    {
        result += my_func(root->child[i]);
    }
    return result;
}

But this is really bad, for 2 reasons:

  1. I am not summing weights of all children.

  2. when I reach leaf child, I am summing -1 while I should add 0.

Source: Windows Questions C++

LEAVE A COMMENT