Amazon Interview Question SDE1s
Country: United States
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).
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
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;
}
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();
}
}
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();
}
}
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.
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;
}
}
}
TreeIterator class can be implemented as follows:
- Reader May 05, 20131. 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.