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);
}
Got a thought to share or found a bug in the code? We'd love to hear from you: