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)


void connect(Node parent)
    if (parent == null)

    // 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;
        if (uncle.right != null) // Consider right child, if left is null
            siblingOfRightChild = uncle.right;
        // 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;
            parent.left.sibling = siblingOfRightChild;

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


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:

Email: (Your email is not shared with anybody)

Facebook comments:

Site Owner: Sachin Goyal