Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

On my interview for an internship, I was asked following question:

On a whiteboard write the simplest algorithm with use of recursion which would take a root of a so called binary tree (so called because it is not strictly speaking binary tree) and make every child in this tree connected with its sibling.

So if I have:

       1 
     /   \   
    2     3   
   / \     \   
  4   5     6   
 /           \ 
7             8

then the sibling to 2 would be 3, to four five, to five six and to seven eight.

I didn't do this, although I was heading in the right direction. Later (next day) at home I did it, but with the use of a debugger. It took me better part of two hours and 50 lines of code. I personally think that this was very difficult question, almost impossible to do correctly on a whiteboard.

How would you solve it on a whiteboard? How to apprehend this question without using a debugger?

share|improve this question
8  
Your description of the question is unclear ('sibling' would imply nodes with the same parent, but your description links nodes which are neighbours at the same depth). Either way, it doesn't seem too hard to me. You clearly failed the question; I'm not sure why you feel the need to complain about it here. –  ipeet Feb 5 '12 at 17:07
    
@smallB: this is a Q&A website. Asking just for our opinions already costed you a few downvotes and a risk for this question to be closed. I edited it to be more constructive. Feel free to revert it and edit it yourself. –  MainMa Feb 5 '12 at 17:12
    
#ippet sibling in this particular case means "the closest node on the same level", just as I've explained in the first line under the "tree" –  smallB Feb 5 '12 at 17:19
2  
What do you mean by "make connected"? –  CodesInChaos Feb 5 '12 at 18:06
    
#Codeinchaos make connected means that they have a pointer to it's sibling. Just in exactly same way parent is connected to its children, and children are connected to their parent. –  smallB Feb 6 '12 at 7:01
show 5 more comments

7 Answers 7

up vote -10 down vote accepted

This is I believe the cleanes solution to your problem:

typedef std::map<int,std::vector<Node*>> tree;

void load_tree(int level, Node* node, tree& nodes)
{
    if (node)
    {
        nodes[level].push_back(node);
        load_tree(++level,node->l_,nodes);
        load_tree(level,node->r_,nodes);
    }
}

unsigned tree_height(Node* root)
{
    if (!root)
    {
        return 0;
    }
    else
    {
    return 1 + max(tree_height(root->l_),tree_height(root->r_));
    }
}

void connect_siblings(tree& nodes,unsigned counter)
{
    for (unsigned i = 0; i < counter; ++i)
    {
        for (auto beg = nodes[i].begin(),end  = nodes[i].end(), sibling = beg; beg != end; ++beg)
        {
            sibling = (beg + 1);
            if (sibling != end)
            {
            (*beg)->s_ = *sibling;
            }
        }
    }
}

In my opinion this question is waaay too hard for someone who applies for an internship position. It requires too much coding. This is not a quesition for a whiteboard.
I believe that either people who were interviewing you didn't really realized the complexity of it or you were given the question with the aim that you won't be able to answer it (read: they already found a person for the position they wanted to fill and you were just being given curtesy of being interviewed).
Anyway, don't fill bad about not being able to answer to it. Most so called professionals (as glaringly proved here) wouldn't be able to do it either. Not on a whiteboard and not within an hour.
Good luck in your future interviews!

share|improve this answer
6  
* It's not necessary to calculate the tree height. * There is no need to make a list of nodes by level if you are going to connect them later. Just keep track of the last node on a level as you connect them. * Even if 'most professional programmers' could not solve this problem, there are a lot of companies who are not interested in most programmers, but are only interested in the ones who can solve problems like this one at a whiteboard. I recently interviewed with a well-known company and was given several problems comparable to this one. –  kevin cline Feb 6 '12 at 14:44
5  
most problems are too hard if you don't know how to solve them. –  Kevin Feb 6 '12 at 15:22
4  
+1 Nice sarcastic reaction to the OP's comments on the other answers. Oh wait, it was sarcasm, wasn't it? –  Christian Rau Feb 6 '12 at 16:35
add comment

In C++, using appropriate STL data structures, this should be just a few lines of code, outlined here:

typedef std::map<int, std::vector<node>> nodes_by_level;

join_siblings(int level, const tree& t, nodes_by_level& nodes) {
  if (t.root()) { 
    nodes[level].push(t.root());
    join_siblings(level + 1, t.left_subtree(), nodes);
    join_siblings(level + 1, t.right_subtree(), nodes);
  }
}

nodes_by_level join_siblings(const tree& t) {
  nodes_by_level nodes;
  join_siblings(0, t, nodes);
  return nodes;
}

There are a fair number of undergraduate CS students who can see this solution immediately, and it seems they were looking for those students.

If you have any ambition as a C++ programmer, and aren't already intimately familiar with the data structures and algorithms provided by the STL, you should learn them now. It seems your competition already has.

share|improve this answer
add comment

I don't think this question is unreasonably hard. It's certainly not trivial, but a good programmer should be able to write it with minor mistakes in a few minutes.

50 lines of code would indeed be pretty long for a whiteboard question, but this question can be solved in much less code.

  • Walk the tree recursively, keeping track of the depth.
  • Have a vector<Node*> with a size corresponding to the depth of the tree(or grow it dynamically) with the elements initialized to null.
  • On use the current depth to index into that vector and declare the current element and the element in the vector "siblings".
  • Set the element in the vector to the current element.

I guess that'd be about 10-15 lines, which should be manageable.

Slightly simplified code:

List<Node> prevNodeAtDepth;
Walker(root, 0);

void Walker(Node node, int depth)
{
    var prev = prevNodeAtDepth[depth];
    if(prev != null)
    {
        Sibling(prev, node);
    }

    prevNodeAtDepth[depth] = node;
    foreach(var child in node.Children)
    {
        Walker(child, depth + 1);
    }
}

void mark_all_siblings(node* root_node)
{
  vector<node*> prev_node_at_depth();
  walker(prev_node_at_depth, root_node, 0);
}

void walker(vector<node*>& prev_node_at_depth, node* node, int depth)
{
    if(depth >= prev_node_at_depth.size())
      prev_node_at_depth.add(nullptr);          

    node* prev = prev_node_at_depth[depth];
    if(prev != nullptr)
    {
        mark_siblings(prev, node);
    }

    prev_node_at_depth[depth] = node;
    if(node.left_child() != nullptr)
        walker(prev_node_at_depth, node.left_child(), depth + 1);
    if(node.right_child() != nullptr)
        walker(prev_node_at_depth, node.right_child(), depth + 1);
}
share|improve this answer
1  
#codeinchaos so now despite the fact that your code doesn't work you have 35 lines of code instead of 10-15 as you claimed. And you have your compiler, debugger, time and most of all you're stress free. Now you see why I think this question was bit too hard for someone who applied for an intership position? How would you fit those lines on whiteboard? You'd have to erase some of them, but then would you remember those erased parts? It is just not as easy as it seems on the first look. –  smallB Feb 6 '12 at 6:52
1  
there is nothing to port. Your so called 15 line solution which if you put parentheses where needed is more like 40+ lines it still doesn't work. There is nothing to port. Give me working solution and I'll port it. No problem. –  smallB Feb 6 '12 at 7:20
2  
@smallB "Professionalls would have difficulties to do it on a whiteboard." That says alot about those professionals! Please, get over this. It's a not-so-hard question to test your understanding of trees and how to operate on them. You couldn't handle it, end of story! Your knowledge did not match what they were requiring. That's all. Don't blame them for asking. –  Sjoerd Feb 6 '12 at 15:06
2  
@smallB Well honestly, every 2nd year CS student should be able to come up with this solution. They didn't ask you about working code, but an algorithm. I'm pretty sure they would have been perfpectly satisfied with the answerer's first 10 lines of pseudocode, which perfectly demonstrate the algorithm. The interviewers also know that nobody can come up with a working program on a whiteboard in 3 minutes. They just wanted a simple algorithm of 10 lines of pseudocode maximum. –  Christian Rau Feb 6 '12 at 16:23
1  
@smallB So don't blame the answerer if you're not able to transform these 10 lines into some working code on your own, which hasn't been the question, anyway! –  Christian Rau Feb 6 '12 at 16:23
show 8 more comments

I don't think the question was difficult. I think they were simply testing if you're comfortable parsing a tree recursively. Obviously, if you haven't done it before, it'll seem very difficult on the spot. On the other hand, now that you have actually done it, you will definitely know in interview how to answer "recurively-parsing-trees" questions.

My point is, the question doesn't seem to "exotic" or "far fetched", it's almost pretty standard. There's no shame in not knowing it beforehand (especially since you mention it's an internship position, so I'm assuming you're still in college), but I guess this is what they wanted to test.

share|improve this answer
    
don't you think that over 50 lines of code is bit too much? unless you can come up with something much shorter. I'd think that 20 lines of code would be the max one should have to do on a whiteboard. There is just isn't space on it for more. –  smallB Feb 5 '12 at 17:22
    
by the way the minus one is not from me. –  smallB Feb 5 '12 at 17:26
    
I don't think lines of code should be an indication of the complexity of an exercise. A language like Scheme or even Python would fit perfectly for this kind of situation and would probably resolve the issue in half what you wrote. Again, certain programmers parse trees every day, multiple times a day. I guess they wanted to test if you're that kind of programmer or not (for the record, there's absolutely nothing wrong in not being that kind, if only that you probably don't match the requirements for the position). –  rahmu Feb 5 '12 at 17:26
    
#rahmu, but it wasn't python, nor was it scheme. It was specific C++. And I do understand and also am able to parse it (I did it next day), the only thing I'm saying that it is unreasonable to expect something like that from a someone who applies for the position of an internship. Just for fun, try to do it yourself on a half of piece of paper and see if you can do it. –  smallB Feb 5 '12 at 17:42
3  
@smallB I'm pretty sure the interviewers didn't want to see a working C++ program on a whiteboard. They're not idiots, man. The question was about an algorithm. Of course there is a huge difference between a general algorithm and a working program, but the latter doesn't belong on a whiteboard, whereas the former is really just some 10-lines of code large. –  Christian Rau Feb 6 '12 at 16:28
show 1 more comment

This problem is solved using a queue based order level traversal.

http://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal

You start by enqueuing the root node. You then push something on the queue that acts like a separator. Each time you deque an item, you push the left/right child of what you just removed from the queue onto the end of the queue. When you deque a separator, you enqueue another separator. You can envision "groupings" of each level in the queue by each separator.

EQ 1, EQ | (separator) : Q(1|)
DQ 1, EQ 2, EQ 3       : Q(|23)
DQ |, EQ |             : Q(23|)
DQ 2, EQ 4, EQ 5       : Q(3|45)
DQ 3, EQ 6             : Q(|456)
DQ |, EQ |             : Q(456|)
DQ 4, EQ 7             : Q(56|7)
DQ 5                   : Q(6|7)
DQ 6, EQ 8             : Q(|78)
...

The high level view of the Q (if we never dequed anything)
1|23|456|78

This is one of four basic types of tree traversal. You have preorder, postorder, inorder and levelorder. This is a data structures 101 traversal type, which is probably why they wanted you to do it.

Personally, I wouldn't have asked for this one in an interview as it is not that common, but I would have asked for pre/post which anyone who has had data structures should know.

EDIT: The terminators are used to group each level. You can do this either recursively or iteratively.

share|improve this answer
    
The separator trick is cute. Need to remember that one. If I'd written a breadth-first traversal, I would have put (Node, depth) tuples in the queue. –  CodesInChaos Feb 5 '12 at 22:39
    
Your answer isn't recursive though, which seems to have been an explicit requirement. –  CodesInChaos Feb 5 '12 at 22:42
    
One interesting difference between out solutions is the memory usage. Your code takes as much memory as the largest generation, whereas mine takes as much as the depth of the tree. Both are proportional to the number of nodes, but favor different tree forms. –  CodesInChaos Feb 5 '12 at 22:44
    
I added a note that says it can be iterative or recursive. Any solution that is iterative can also be recursive. stackoverflow.com/questions/2659854/recursion-vs-loops –  jmq Feb 5 '12 at 22:50
    
That post is about transforming between the built in stack, and an explicit stack. While you can rewrite queue based algorithms to recursion, it is a very bad fit. –  CodesInChaos Feb 5 '12 at 22:52
add comment

I completed kevincline's answer to include a tree class and also made some minor changes for convenience. Please note that naked pointers are not a good practice and are only used for the sake of this example.

Here is the complete, compileable code:

#include <iostream>
#include <map>
#include <vector>

class Tree {
public:
    explicit Tree(int value) : _root(NULL), _left(NULL), _right(NULL), _sibling(NULL), _nodeValue(value) {}
    ~Tree() { if (_left) delete _left; if (_right) delete _right; }
    Tree* root() const { return _root; }
    Tree* left_subtree() const { return _left; }
    Tree* right_subtree() const { return _right; }
    Tree* sibling() const { return _sibling; }
    int value() const { return _nodeValue; }    
    Tree* setLeft(Tree* t) { t->_root = this; return _left = t; }
    Tree* setRight(Tree* t) { t->_root = this; return _right = t; }
    void connect(Tree* s) { _sibling = s; }
private:
    Tree* _root;
    Tree* _left;
    Tree* _right;
    Tree* _sibling;
    int _nodeValue;    
};

typedef std::map<int, std::vector<Tree*> > nodes_by_level;

void join_siblings(int level, Tree* t, nodes_by_level& nodes) {
    if (!t) return;
    nodes[level].push_back(t);
    join_siblings(level + 1, t->left_subtree(), nodes);
    join_siblings(level + 1, t->right_subtree(), nodes);
}

nodes_by_level join_siblings(Tree& t) {
  nodes_by_level nodes;
  join_siblings(0, &t, nodes);
  return nodes;
}

void printSiblings(Tree* t) {
    if (!t) return;
    if (t->sibling()) std::cout << "The sibling of " << t->value() << " is " << t->sibling()->value() << std::endl;
    printSiblings(t->left_subtree());
    printSiblings(t->right_subtree());
}

int main() {
    Tree t(1);
    Tree* two = t.setLeft(new Tree(2));
    Tree* three = t.setRight(new Tree(3));
    Tree* four = two->setLeft(new Tree(4));
    two->setRight(new Tree(5));
    Tree* six = three->setRight(new Tree(6));
    four->setLeft(new Tree(7));
    six->setRight(new Tree(8));

    nodes_by_level nl = join_siblings(t);

    std::cout << "Connected nodes: \n";

    for (nodes_by_level::iterator it = nl.begin();
         it != nl.end();
         ++it) {
        std::vector<Tree*>& v = it->second;
        for (size_t i = 0; i < v.size(); ++i) {
            if (i < v.size() - 1) v[i]->connect(v[i+1]);
        }
    }

    printSiblings(&t);

    return 0;
}

Output is:

Connected nodes: 
The sibling of 2 is 3
The sibling of 4 is 5
The sibling of 7 is 8
The sibling of 5 is 6

In total, it is 73 lines (including the empty lines as well). In an interview, you don't need to implement the code for the tree class and to build the tree itself, and to display the siblings like this. What they are interested in is the 14 lines of code that kevincline gave you as an answer.

Since this site is about professional advice, here is mine. Don't blame the failure on external factors. Here, you are trying to prove that the question was unreasonably hard, but it wasn't. You failed, but don't be offended. Look at it as an opportunity to improve yourself. Imagine if you didn't fail this interview and later screwed up something in production. Now you know an area where you can improve. That's great, take that chance. Next time, you can be much more confident in a similar interview.

share|improve this answer
    
#Tamas There cannot possibly be connection between 2 and 3 4 and 5 and 6 and 7 and 8. The reason for that is that they don't have a member for it. What you need is additional member Node* sibling. All what you did is copied kevin's answer which is preorder iteration over a tree. I know how to do it. I knew how to do it. Nodes after your algorithm finishes will not be connected. It is most appreciated your's and others effort. I believe that it is not as easy as it looks. But thank you of course for your effort. Try to connect them if you could. Thanks. –  smallB Feb 6 '12 at 12:58
    
#Tamas will check if you replied in about an hour. –  smallB Feb 6 '12 at 12:59
    
I updated my answer. –  Tamás Szelei Feb 6 '12 at 13:27
    
#Tamas ok thanks +1 most appreciated.Just to make it clear, I do not blame them, I do understand that it is me who didn't know the answer, the only concern I have that this question required too much coding for an internship position. How many lines your updated answer (just algorithm to read in tree and connect) has? Was it that obvious for you how to do it? Did you get it from the first time? I'm assuming you're professional and you've had lots of experience with this structures, and yet I'm sure that you have to give some thought and try if it works. That's all.Any way, thank you for answer –  smallB Feb 6 '12 at 14:29
2  
+1 for whole answer, but I want to especially highlight Don't blame the failure on external factors. –  Sjoerd Feb 6 '12 at 15:07
show 4 more comments

This is simple. Write an in order traversal. The implementation is standard. Modify it to pass depth into the callback. The standard implementation passes a data pointer to the callback. Use it to pass a map<int,vector<node*> >. the key is depth and the value is the list of nodes at that level. Your callback uses the passed in depth to add the current node. It's both short and mostly standard code.

class Tree {
    Node* root;

    private:

    // tree impl here

    private:

    // standard inorder traversal code
    static void inorder(Node* node, int depth, map<int,list<Node*> >& m) {
        if (node == NULL) return;
        inorder(node->left,depth+1,m);
        m[depth].push_back(node);
        inorder(node->right,depth+1,m);
    }

    public:
    // just call inorder passing a map and the root pointer
    void group_by_depth(map<int, list<Node*> >& m) {
        inorder(root,0,m);
    } 
}

I haven't written c++ in about 2 years now, so hopefully this compiles for you. Either way the idea should be clear.

share|improve this answer
    
#Kevin ok, if it's that simple, could you post the correct working code. So far no one did, everyone said that this is simple. –  smallB Feb 6 '12 at 6:55
3  
@smallB It's a whiteboard assignment, there is no "correct working code" requirement. Kevin's answer is good enough in practice, as he shows that he knows what he is talking about, and his answer mentions the details that pop up while implementing ("pass depth", "pass map", "key is depth, value is list of nodes at that level"). –  Sjoerd Feb 6 '12 at 15:15
    
@smallB Try this C++ code, which should be good enough for a whiteboard assignment: void callback(int depth, Node& node, /* std::map<int, std::vector<Node*> >* */ void* data) { /*...*/ } and std::map<int, std::vector<Node*> > node_map; tree.traverse_preorder(&callback, (void*)&node_map);. –  Sjoerd Feb 6 '12 at 15:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.