CareerCup

A simple recursive algorithm. Not checking for null because I am assuming Node[] children only contains non-null.

public class RightSibling {
    class Node { 
        public Node[] children; 
        public Node right; 
    }

    public void populateRightSiblings(Node node) {
        for(int i=0; i<children.length; i++) {
            Node child = node.children[i];
            if(i < children.length - 1) {
                child.right = node.children[i+1];
            }
            populateRightSiblings(child);
        }
    }
}

Here's an approach with O(d) extra space, where d is the depth of the tree.

public void populateRightSiblings(Node root) {
	if (root == null || root.children == null || root.children.length < 2) {
            return;
        }
        Deque<Node> queue = new ArrayDeque<Node>();
        List<Node> rightMost = new ArrayList<>();
	queue.addLast(root);
        int level = 0;
        int currentLevelCount = 1;
        int nextLevelCount = 0;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            Node [] children = node.children;
            nextLevelCount += children.length;
            currentLevelCount--;
            if (currentLevelCount == 0) {
                level++;
                currentLevelCount = nextLevelCount;
                nextLevelCount = 0;
            }
            for (int i = 0; i < children.length-1; i++) {
                children[i].right = children[i+1];
            }
            if (level >= rightMost.size()) {
                rightMost.add(children[children.length-1]);
            } else if (children != null && children.length != 0) {
                rightMost.get(level).right = children[0];
                rightMost.set(level, children[children.length-1]);
            }
        }
   }

private static class Node {
public Node[] children;
public Node right;
private int value;

public Node(int value) {
this.value = value;
}

private void populateRightSiblings(Node node) {
if (node == null || node.children == null || node.children.length < 2)
return;

if (node.children.length > 1) {
Node lastChild = node.children[node.children.length - 1];
node.right = lastChild;
}

for (Node child : node.children) {
populateRightSiblings(child);
}
}

@Override
public String toString() {
return String.valueOf(value);
}
}

public static void main(String[] args) {
Node _1 = new Node(1);
Node _6 = new Node(6);
Node _8 = new Node(8);
Node _11 = new Node(11);
Node _13 = new Node(13);
Node _15 = new Node(15);
Node _17 = new Node(17);
Node _22 = new Node(22);
Node _25 = new Node(25);
Node _27 = new Node(27);

_1.children = new Node[]{_6};
_8.children = new Node[]{_1,_11};
_13.children = new Node[]{_8,_17};
_17.children = new Node[]{_15,_25};
_25.children = new Node[]{_22,_27};

Node root = _13;
root.populateRightSiblings(root);
System.out.println(root);
}

private static class Node {
public Node[] children;
public Node right;

private void populateRightSiblings(Node node) {
if (node == null || node.children == null || node.children.length < 2)
return;

if (node.children.length > 1) {
Node lastChild = node.children[node.children.length - 1];
node.right = lastChild;
}

for (Node child : node.children) {
populateRightSiblings(child);
}
}
}

/**
     * @author Omid Ghiasi Tarzi
     */
    static void setRights(Node node) {
        Node preNode = null;
        for (Node child : node.children) {
            child.right = preNode;
            preNode = child;
            setRights(child);
        }
    }