## Booking.com Interview Question

SDE-2s**Country:**United States

This is incomplete. At depth 2 the right of the first child's right most child is not set accurately. How about this (in python):

```
class Node(object):
def __init__(self, value, children = None, right = None):
if children:
self.children = children
else:
self.children = []
self.right = right
self.value = value
def show(self, tab = 0):
print ("{0} Item {1}".format("\t" * tab, self.value))
print ("{0} Right {1}".format("\t" * tab, self.right))
for c in self.children:
c.show(tab + 1)
def setRight(root)
q = list()
q.append(root)
q.append(None)
while len(q) > 0:
n = q[0]
q.remove(n)
if n != None:
for item in n.children:
q.append(item)
if len(q) > 0:
if q[0] != None:
n.right = q[0]
else:
q.append(None)
root.show(0)
```

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);

}

}

}

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

- Sunny August 19, 2015