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 *parentsib, Node *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);
}
}```