Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Populate sibling pointer in each node for level order traversal

Problem: Given a binary tree order, populate sibling pointer in each node so that level order traversal can be done easily

Example: The blue arrows shown below are the sibling pointers (also known as nextRight pointers)

Code:
```
void connect(Node parent)
{
if (parent == null)
return;

// Sibling for the right child will lie in children
// of current parent's sibling
// We need to find this distant cousin, even if current
// parent's right child is null

Node siblingOfRightChild = null;
Node uncle = parent.sibling;
while (uncle != null)
{
if (uncle.left != null) // Give preference to left child
{
siblingOfRightChild = uncle.left;
break;
}
if (uncle.right != null) // Consider right child, if left is null
{
siblingOfRightChild = uncle.right;
break;
}
// Uncle does not have any children, move to next uncle
uncle = uncle.sibling;
}

if (parent.left != null)
{
if (parent.right != null)
parent.left.sibling = parent.right;
else
parent.left.sibling = siblingOfRightChild;
}

if (parent.right != null)
parent.right.sibling = siblingOfRightChild;

connect(parent.left);
connect(parent.right);
}

```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: