Trees and Graphs‎ > ‎

Set Binary Tree Sibling Pointers

Given a binary tree with node structure containing an extra pointer called sib (for sibling) which is currently set to garbage value, write a function which sets the sib pointer to it's immediate right node in the same level. If such node doesn't exist, set sib to null.


                O->null
       / \
      O-->O->null
     /   / \
    O-->O-->O->null
       /
      O->null


void SetTreeSib(Node *root)
{
    root->sib = nullptr;
    SetTreeSibHelper(root);
}
 
void SetTreeSibHelper(Node *n)
{
    if (nullptr == n)
        return;
    if (nullptr != n->right)
        SetNodeSib(n->sib, n->right);
    if (nullptr != n->left)
    {
        if (nullptr != n->right)
            n->left->sib = n->right;
        else
            SetNodeSib(n->sib, n->left);
    }
 
    // Note the importance of calling with the right child first
    SetTreeSibHelper(n->right);
    SetTreeSibHelper(n->left);
}
 
void SetNodeSib(Node *parentsibNode *child)
{
    while (nullptr != parentsib)
    {
        if (nullptr != parentsib->left)
        {
            child->sib = parentsib->left;
            return;
        }
        if (nullptr != parentsib->right)
        {
            child->sib = parentsib->right;
            return;
        }
 
        parentsib = parentsib->sib;
    }
 
    child->sib = nullptr;
}

Iterative solution, using level-order traversal:
public void SetTreeSibIterative<T>(Node<T> n)
{
    Queue<Node<T>> q = new Queue<Node<T>>();
    q.Enqueue(n);
    q.Enqueue(null);
 
    while (q.Count > 0)
    {
        n = q.Dequeue();
        if (n == null)
        {
            if (q.Count > 1)
                q.Enqueue(null);
            continue;
        }
 
        if (q.Count > 0)
            n.sib = q.Peek();
        else
            n.sib = null;
 
        if (n.left != null)
            q.Enqueue(n.left);
        if (n.right != null)
            q.Enqueue(n.right);
    }
}