Make delicious recipes!

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:

Facebook comments:

Site Owner: Sachin Goyal