## Amazon Interview Question for SDE1s

Country: United States

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

TreeIterator class can be implemented as follows:
1. List<T> data member to store the tree node values. We can initiliaze this data member on call of .begin() method. Initiliazation will populate the list in "inorder" fashion.
2. Next() returns bool value based on length and position of current list pointer.
3. hasNext() returns the next tree node as per the list data member.

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

Good solution. This may require O(n) extra space though. How about doing the inorder traversal using iteration? hasNext() will check whether the next iteration is possible and next() would return the element of the current iteration.

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

For implementing the Iterator {} for binary_tree....
the choice of Node {} structure would help, if parent pointer is stored
in the Node then we can do it without using extra space, otherwise O(h) space would be required.. where h = height = longest distance
from root to the leaves in worst case it would be O(n) and best/Average it would be O(lgn).

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

Intuitively we use recursion to traverse a tree structure and that takes at most O(logN) stack space. Therefore, no matter what we do, we cannot achieve worse case of O(1) space complexity. Having said that, our best effort will enable us to only use O(logN) space instead of O(N), putting the entire Tree in a List with in-order traversal.

We can use a stack structure to keep track of which node we are currently visiting. By in-order traversal, we visit all the left nodes, then root, then right. Thus, we push all the left nodes to the stack, and next() returns the left most node on the stack. If there are none, return the root and push the right node onto the stack. We simply repeat till we printed everything.

Here's the structure of the tree node:

``````public class BinaryTreeNode<T> {

public T item;
public BinaryTreeNode<T> left;
public BinaryTreeNode<T> right;

public BinaryTreeNode(T item){
this.item = item;
left = null;
right = null;
}
}``````

Here's the iterator class:

``````import java.util.Stack;

public class InOrderIterator<T> {

private BinaryTreeNode<T> tree;
private Stack<BinaryTreeNode<T>> stack;
private boolean flag;	//Indicates if we have added the left most node

public InOrderIterator(BinaryTreeNode<T> t){
tree = t;
stack = new Stack<BinaryTreeNode<T>>();
BinaryTreeNode<T> current = tree;
while(current != null){
stack.push(current);
current = current.left;
}
flag = true; //We have added all left most nodes
}

public boolean hasNext(){
return !stack.isEmpty();
}

public T next(){
BinaryTreeNode<T> current = stack.peek();
//Push all left nodes if there is any
if(!flag){
while(current.left != null) {
stack.push(current.left);
current = current.left;
flag = true;	//We have now added all the left most nodes
}
//If both left == null, then we won't have any more left sub-trees to add
if(current.right == null) flag = true;
}
//At this point, there is no more left node from the top of the stack
current = stack.pop();
if(current.right != null) {
stack.push(current.right);
flag = false; //We may have more left sub-trees to add now that the right sub-tree is added
}
return current.item;
}

}``````

Here's a test code to test it out:

``````public class Test{

public static void main(String[] args){
BinaryTreeNode<Integer> tree = Tree.makeBalancedTree(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11});
System.out.println();
InOrderIterator<Integer> itr = new InOrderIterator<Integer>(tree);
while(itr.hasNext()) System.out.print(itr.next() + " ");
}

public static BinaryTreeNode<Integer> makeBalancedTree(int[] array){
return addToTree(array, 0, array.length-1);
}

private static BinaryTreeNode<Integer> addToTree(int[] array, int start, int end){
if(end < start) return null;
int mid = (start+end)>>1;
BinaryTreeNode<Integer> n = new BinaryTreeNode<Integer>(new Integer(array[mid]));
n.left = addToTree(array, start, mid - 1);
n.right = addToTree(array, mid + 1, end);
return n;
}
}``````

The output is:

1 2 3 4 5 6 7 8 9 10 11

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

``````Node inorder_walk(Node current, Node parent){
if (current == null)
return null;
if (current.left == null && current.right == null){ //it's leaf
current.next = parent;
return current;
}
Node tmp1 = inorder_walk(current.right , parent);
Node tmp2 = inorder_walk(current.left , current);
current.next = tmp1;
if (tmp2 == null)
return current;
return tmp2;
}
class Node{
Node right , left , next;
}``````

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

The method inorder_walk has to be initially called as :

``inorder_walk(root , root);``

by use of this method we can update next field of every Node

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

``````public class Iterator<T>{
Stack<BinaryTreeNode<T>> s;
public Iterator(BinaryTreeNode<T> t){
s = new Stack<BinaryTreeNode<T>>();
fillStack(t);
}
void fillStack(BinaryTreeNode<T> current){
if (current == null)
return;
fillStack(current.left);
s.push(current);
fillStack(current.right);
return;
}
public boolean hasNext(){
return !s.isEmpty();
}
public T next(){
if (s.isEmpty)
return null;
return s.pop();
}
}``````

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

``````public class Iterator<T>{
Stack<BinaryTreeNode<T>> s;
public Iterator(BinaryTreeNode<T> t){
s = new Stack<BinaryTreeNode<T>>();
fillStack(t);
}
void fillStack(BinaryTreeNode<T> current){
if (current == null)
return;
fillStack(current.left);
s.push(current);
fillStack(current.right);
return;
}
public boolean hasNext(){
return !s.isEmpty();
}
public T next(){
if (s.isEmpty)
return null;
return s.pop();
}
}``````

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

iteratively in-order traverse.

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

I had the same question, but I was told that I could not use an extra data structure.

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

With no parent link, it has to use extra memory. Stack or linked list to track the order.
With parent link, we can divide it into 2 cases.
a) the current iterator has right subtree. the next node is the leftmost node in this right subtree.
b) the current iterator has no right subtree, go up to ancestor's node. UNTIL
if the ancestor node is left child of it's parent's node, that ancestor's parent node is the next node.

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

``````interface Iterator<T>
{
boolean hasNext();
I next();
}

class Node
{
int data;
Node left;
Node right;
}

class InterviewQuestion implements Iterator<Node>
{
Node root;

InterviewQuestion(Node root)
{
this.root = root;
}

boolean hasNext()
{
return root != null;
}

Node next()
{
if(root == null)
{
return null;
}

Node current = root;
Node parent = null;

while(current.left != null)
{
parent = current;
current = current.left;
}

if(parent == null)
{
root = root.right;
}

if(current.right != null)
{
parent.left = current.right;
}else
{
parent.left = null;
}

return current;
}

}``````

}

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.

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