## Amazon Interview Question

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

```
void connect(Node root) {
if(root != null)
connect(root, 0, new Vector<Node>());
}
void connect(Node root, int level, Vector<Node> links) {
Node prev = null;
prev = links.get(level);
if(prev != null) {
prev.next = root;
}
links.replace(level, root);
if(!isLeaf(root)) {
if(root.left != null)
connect(root.left, level + 1, links);
if(root.right != null)
connect(root.right, level + 1, links);
}
}
```

Hi.. I have a doubt on this question.

By 'connect' do you mean that each node must store a reference to all nodes at the same level?

If yes, then this reference storage itself cannot be achieved in O(1) space because as the height of the tree increases, every node will have more number of peers.

It would be helpful to think about this problem if you can explain.

Thanks,

Pravin

This can be done in O(n) with O(1) space by doing the following (in java)

```
class Node{
int data;
Node left, right, nextRight;
}
public static void setupLevels(Node leftMost){
Node lastOnLevel, nextOnLevel, firstOnLevel;
//while still computing levels
while(leftMost != null){
//while there are still Nodes in the parent level
while(leftMost != null){
//if there is a new left child to consider
nextOnLevel = leftMost.left;
if(nextOnLevel != null){
//if there is a previous child, attach the last child to the new one
if(lastOnLevel != null){
lastOnLevel.nextRight = nextOnLevel;
}
lastOnLevel = nextOnLevel;
}
//capture the first non-null child
if(lastOnLevel != null && firstOnLevel == null){
firstOnLevel = lastOnLevel;
}
//if there is a new right child
nextOnLevel = leftMost.right;
if(nextOnLevel != null){
//if there is a previous child, attach the last child to the new one
if(lastOnLevel != null){
lastOnLevel.nextRight = nextOnLevel;
}
lastOnLevel = nextOnLevel;
}
//capture the first non-null child
if(lastOnLevel != null && firstOnLevel == null){
firstOnLevel = lastOnLevel;
}
//move to the next parent
leftMost = leftMost.nextRight;
}
//prep for the next level
leftMost = firstOnLevel;
firstOnLevel = null;
lastOnLevel = null;
}
}
```

```
public class Node
{
int value;
Node left;
Node right;
Node next;
}
public void connectNodes(Node n)
{
if(n==null)
{
return;
}
Node rightSibling=getNextSiblingChild(n.next);//Iteratively visit the right sibling of n until we find a node that has at least one child.
if(n.left!=null && n.left!=null)
{
n.left.next=n.right;
n.right.next=rightSibling;
}else if (n.left!=null && n.right==null)
{
n.left.next=rightSibling;
}else if (n.right!=null && n.left==null)
{
n.right.next=rightSibling;
}
connectNodes(n.left);
connectNodes(n.right);
}
private Node getNextSiblingChild(Node n)
{
while(n!=null)
{
if(n.left!=null)
{
return n.left;
}else if(n.right!=null)
{
return n.right;
}
n=n.next;
}
}
```

//O(n) time. O(1) space.

```
public void connectSameLevelNodes() {
if (root == null) {
return;
}
int maxDepth = findMaxDepth(root, 0);
System.out.println("MAX DEPTH " + maxDepth);
for (int i = 1; i < maxDepth; i++) {
connectNodesOnSameLevel(root, 0, i, null);
}
}
private Node connectNodesOnSameLevel(Node root, int currentDepth, int level, Node previousNode) {
if (root == null) {
return previousNode;
}
if (currentDepth == level) {
if (previousNode == null) {
return root;
} else {
previousNode.nextRight = root;
return root;
}
} else {
Node left = connectNodesOnSameLevel(root.left, currentDepth + 1, level, previousNode);
previousNode = connectNodesOnSameLevel(root.right, currentDepth + 1, level, left == null ? previousNode : left);
}
return previousNode;
}
private int findMaxDepth(Node root, int depth) {
if (root == null) {
return depth;
}
return Math.max(findMaxDepth(root.left, depth + 1), findMaxDepth(root.right, depth + 1));
}
```

```
public void connectSameLevelNodes() {
if (root == null) {
return;
}
int maxDepth = findMaxDepth(root, 0);
System.out.println("MAX DEPTH " + maxDepth);
for (int i = 1; i < maxDepth; i++) {
connectNodesOnSameLevel(root, 0, i, null);
}
}
private Node connectNodesOnSameLevel(Node root, int currentDepth, int level, Node previousNode) {
if (root == null) {
return previousNode;
}
if (currentDepth == level) {
if (previousNode == null) {
return root;
} else {
previousNode.nextRight = root;
return root;
}
} else {
Node left = connectNodesOnSameLevel(root.left, currentDepth + 1, level, previousNode);
previousNode = connectNodesOnSameLevel(root.right, currentDepth + 1, level, left == null ? previousNode : left);
}
return previousNode;
}
private int findMaxDepth(Node root, int depth) {
if (root == null) {
return depth;
}
return Math.max(findMaxDepth(root.left, depth + 1), findMaxDepth(root.right, depth + 1));
}
```

A little deviation from the above approach, I am also using recursion to link the nodes at the same level.

Approach is to use recursion to reach the desired level and if the left child and right child both are not null then running through the next pointers of the left child until we reach the end and then linking it with the right child.

Returning left child as long as it is not null otherwise we return the right child.

```
public void associateNextPtr(){
// need to associate pointers starting from the root
int level = 2;
while(associateNextPtrAtLevel(root,level)!=null){
level++;
}
System.out.println("total levels are: " + level-1);
}
private Node associateNextPtrAtLevel(Node root, int level) {
Node retVal;
if (root == null) {
retVal = null;
} else if (level == 1) {
retVal = root;
} else {
Node leftChild = associateNextPtrAtLevel(root.left, level - 1);
Node rightChild = associateNextPtrAtLevel(root.right, level - 1);
if (leftChild != null && rightChild != null) {
Node scanNode = leftChild;
while(scanNode.nextNode != null){
scanNode = scanNode.nextNode;
}
scanNode.nextNode = rightChild;
retVal = leftChild;
} else if (leftChild != null) {
retVal = leftChild;
} else {
retVal = rightChild;
}
}
return retVal;
}
```

1st pass - DFS to initialize node.data to the height of this node in a tree.

```
private static int DFSSetHeight(Node n, int h) {
if (n == null) return h - 1;
n.value = h;
return Math.max(DFSSetHeight(n.left, h+1), DFSSetHeight(n.right, h+1));
}
```

then iterate over the height, each iteration spawn a new DFS. so we iteratively go deeper and deeper. during each pass remember to first go to the left son then the right one. also remember the last visited node at the maximum level (per this iteration). when you find a new one at the correct level, connect it with the previous one.

```
private static void DFSSetNextRight(Node n, int toLevel) {
if (n == null) return;
if (n.value == toLevel) {
if (lastAtLevel != null) {
lastAtLevel.nextRight = n;
}
lastAtLevel = n;
return; //we don't need to go deeper
}
DFSSetNextRight(n.left, toLevel);
DFSSetNextRight(n.right, toLevel);
}
```

initialize like this:

```
private static Node lastAtLevel;
public static void main(String[] args) {
Node root = null ; //init tree
int maxH = DFSSetHeight(root, 0);
for (int i = 1; i <= maxH ; i ++ ) {
lastAtLevel = null;
DFSSetNextRight(root, i);
}
}
```

space O(1); time O(N) - last iteration goes through n elements (full tree), last but one through (n/2) etc .. so in total O(3N) including first DFS pass to set up heights.

If we want to achieve this in O(1) space, I assume we have to compromise on Time complexity (natural trade-off between memory and time)

Logic : call following method h times on root (where h is height of tree) and increment depth every time

Method checks if current value of depth is 0 (which means desired depth is achieved) and then attach backup node to current node.

(Please comment for any bug)

```
static prevNode = null;
connectNode(Node root , int depth){
if(root == null)
return;
if(depth == 0){
if(prevNode == null){
prevNode = root;
}
else{
prevNode.nextRight = root;
}
}
else{
connectNode(root.left , depth -1);
connectNode(root.right , depth -1);
}
}
```

If we want to achieve this in O(1) space, I assume we have to compromise on Time complexity (natural trade-off between memory and time)

Logic : call following method h times on root (where h is height of tree) and increment depth every time

Method checks if current value of depth is 0 (which means desired depth is achieved) and then attach backup node to current node.

(Please comment for any bug)

```
static prevNode = null;
connectNode(Node root , int depth){
if(root == null)
return;
if(depth == 0){
if(prevNode == null){
prevNode = root;
}
else{
prevNode.nextRight = root;
}
}
else{
connectNode(root.left , depth -1);
connectNode(root.right , depth -1);
}
}
```

```
static class Node {
int data;
Node left;
Node right;
Node nextRight;
}
public static void setNextRight(Node root){
if(root == null)
return;
setNextRight(root.left, root.right);
setNextRight(root.right, null);
}
public static void setNextRight(Node left, Node nextRight){
if(left == null)
return;
left.nextRight = nextRight;
if(left.left != null)
setNextRight(left.left, left.right);
if(left.right != null)
setNextRight(left.right, nextRight == null ? null : nextRight.left);
}
```

I assume you want to traverse the node level order, and store the same in new singly linked list.

- Maddy September 13, 2015We can achieve it using simple queue,