How to find siblings of a tree?

Question

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?

Answer 1

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!

Answer 2

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.

Answer 3

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);
}

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

This is not an answer, but I just got the same question. I did it recursively with DFS and a vector < stack < Node* > > [level]. But then they asked for constant memory, i.e. iterative. I gave up. My ETA was ~15 min, but I had "couple minutes".

---

I got it. Now it is an answer.
Lesson learned: use what you build.
Algo: iteratively by level, connect siblings (for the root, connect right to left child). Save leftmost as list head. Repeat for all nodes in the list (of connected siblings of previous level). Save leftmost as new list head, etc.