## Amazon Interview Question for SDE-2s

• -1
of 1 vote

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

We can achieve it using simple queue,

Comment hidden because of low score. Click to expand.
0
of 0 votes

Not O(1) space as required

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

Not O(1) memory. Recursion uses memory too.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just do a pre-order or in-order traversal and keep a vector. Time O(n). Space O(log n)

Comment hidden because of low score. Click to expand.
0
of 0 votes

not O(1) space as required.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not O(1) memory. You are using recursion and that requires memory too.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static void connect(Node root) {
if (root != null) connect(root.left, root.right);
}

static void connect(Node root, Node next) {
if (root == null) return;
root.nextRight = next;
connect(root.left, root.right);
if (next != null) connect(root.right, next.left);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def connect(self, root):
import Queue
q = Queue.Queue()
q.put(root)
while not q.empty():
size = q.qsize()
head=None
while size > 0:
r = q.get()
if head:
head.next=r
head=r
if r.left:
q.put(r.left)
if r.right:
q.put(r.right)
size -= 1

return root``````

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More