ConnectSiblings.java

package trees;


public class ConnectSiblings {


    /*
     * Given a binary tree, connect its siblings at each level
     * Runtime Complexity:
     * Linear, O(n)
     *
     * Memory Complexity:
     * Constant O(1)
     *
     * A binary tree is a data structure made up of nodes, where each node contains, besides data, up to two children:
     * "left" reference and "right" reference. Nodes with the same parent node are called siblings.
     * We need to connect all siblings at each level.
     * In level order traversal of a tree, all nodes are processed by depth; first the root, then the children of the
     * root and so on. It is equivalent to a breadth-first-search from the root.
     * Each node in the above binary tree has one more pointer i.e. next (aka sibling) along with the left and
     * right pointers. 'next' is used to connect one node to the other.
     *
     * Given the starting node at level 'x' (where nodes at level 'x' are connected):
     * 1. Traverse the nodes at level 'x' from left to right while connecting the siblings at level 'x+1'.
     *      Now that siblings at level 'x+1' are connected, use the head node (left-most) of level 'x+1' and
     *      apply the same approach on 'x+2'.
     * 2.Keep running these steps till you run out of levels.
     *
     * */

    protected static class Node {
        int data;
        Node left, right, nextRight;

        Node(int item) {
            data = item;
            left = right = nextRight = null;
        }
    }


    private Node root;

    // Sets the next of root and calls connectRecur()
    // for other nodes
    void connect(Node p) {

        // Set the next for root
        p.nextRight = null;

        // Set the next right for rest of the nodes (other
        // than root)
        connectRecur(p);
    }


    protected void connectRecur(Node p) {
        if (p == null) return;

        if (p.left != null) p.left.nextRight = p.right;

        // Set the next pointer for p's right child
        // p->next will be NULL if p is the right most child
        // at its level
        if (p.right != null)
            p.right.nextRight = (p.nextRight != null) ? p.nextRight.left : null;


        connectRecur(p.left);
        connectRecur(p.right);
    }


    public static void main(String args[]) {
        ConnectSiblings tree = new ConnectSiblings();

        /* Constructed binary tree is
             10
            /  \
          8     2
         /
        3
        */
        tree.root = new Node(10);
        tree.root.left = new Node(8);
        tree.root.right = new Node(2);
        tree.root.left.left = new Node(3);


        tree.connect(tree.root);

        System.out.println("Following are populated next pointers in the tree" + "(-1 is printed if there is no next)");

        int a = tree.root.nextRight != null ? tree.root.nextRight.data : -1;
        System.out.println("next of " + tree.root.data + " is " + a);

        int b = tree.root.left.nextRight != null ? tree.root.left.nextRight.data : -1;
        System.out.println("next of " + tree.root.left.data + " is " + b);

        int c = tree.root.right.nextRight != null ? tree.root.right.nextRight.data : -1;
        System.out.println("next of " + tree.root.right.data + " is " + c);

        int d = tree.root.left.left.nextRight != null ? tree.root.left.left.nextRight.data : -1;
        System.out.println("next of " + tree.root.left.left.data + " is " + d);
    }
}