Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
Bfs Iterator
import java.util.*;
class Practice5 {
public static class Node {
public Integer data;
public Node left, right;
public Node(Integer data){
this.data = data;
}
@Override
public String toString(){
return this.data.toString();
}
}
public static class Bst implements Iterable<Node> {
public Node root;
@Override
public Iterator<Node> iterator(){
return root == null ? Collections.emptyIterator() : new NodeIterator(root);
}
}
public static class NodeIterator implements Iterator<Node> {
Node start;
LinkedList<Node> q;
public NodeIterator(Node root){
start = root;
q = new LinkedList<>();
q.add(start);
}
@Override
public boolean hasNext(){
return !q.isEmpty();
}
@Override
public Node next(){
Node ret = q.removeFirst();
if(ret.left != null){
q.add(ret.left);
}
if(ret.right != null){
q.add(ret.right);
}
return ret;
}
@Override
public void remove(){
// empty
}
}
public static void main(String[] args){
Bst bst = new Bst();
bst.root = new Node(19);
bst.root.left = new Node(1);
bst.root.right = new Node(5);
bst.root.left.left = new Node(3);
bst.root.left.right = new Node(242);
for(Node n : bst){
System.out.println(n);
}
}
}
public class Node implements Iterable<Node>
{
private int value;
private Node left;
private Node right;
private Iterator<Node> bti;
public Node(int v)
{
this.value=v;
}
public Iterator<Node> iterator()
{
bti=new BinaryTreeIterator(this);
return bti;
}
public static void main(String[] args)
{
//code to create tree
Node n=new Node(6)
Iterator<Node> treeIt=n.iterator();
while(treeIt.hasNext())
{
System.out.println(treeIt.getNext().value);
}
}
public class BinaryTreeIterator implements Iterator<Node>
{
private Node n;=
public BinaryTreeIterator(Node rt)
{
n=rt;
}
public boolean hasNext()
{
return(n!=null);
}
public Node getNext() throws NoSuchElementException
{
if(hasNext())
{
Node ret=n;
n=n.left!=null?n.left:n.right;
return ret;
}
throw new NoSuchElementException();
}
public void remove() throws UnsupportedOperationException
{
throw new UnsupportedOperationException();
}
}
}
public class Node implements Iterable<Node>
{
private int value;
private Node left;
private Node right;
private Iterator<Node> bti;
public Node(int v)
{
this.value=v;
}
public Iterator<Node> iterator()
{
bti=new BinaryTreeIterator(this);
return bti;
}
public static void main(String[] args)
{
//code to create tree
Node n=new Node(6)
Iterator<Node> treeIt=n.iterator();
while(treeIt.hasNext())
{
System.out.println(treeIt.getNext().value);
}
}
public class BinaryTreeIterator implements Iterator<Node>
{
private Node n;=
public BinaryTreeIterator(Node rt)
{
n=rt;
}
public boolean hasNext()
{
return(n!=null);
}
public Node getNext() throws NoSuchElementException
{
if(hasNext())
{
Node ret=n;
n=n.left!=null?n.left:n.right;
return ret;
}
throw new NoSuchElementException();
}
public void remove() throws UnsupportedOperationException
{
throw new UnsupportedOperationException();
}
}
}
public class BinaryDFSInterator<E> implements Iterator<E>{
private E[] binaryTree;
private boolean[] visited;
private int currentIndex = -1;
public BinaryDFSInterator(E[] binaryTree){
this.binaryTree = binaryTree;
this.visited = new boolean[binaryTree.length];
}
public boolean hasNext(){
return currentIndex != binaryTree.length - 1;
}
public E next(){
if(currentIndex < 0){
currentIndex = 0;
visited[currentIndex] = true;
return binaryTree[currentIndex];
}
if(isLeaf()){
currentIndex = getParent();
}
int nextNotVisitedNode = getNotVisitedChild();
while(nextNotVisitedNode == -1){
currentIndex = getParent();
nextNotVisitedNode = getNotVisitedChild();
}
currentIndex = nextNotVisitedNode ;
visited[currentIndex] = true;
return binaryTree[currentIndex];
}
public void remove(){
throw new UnsupportedOperationException();
}
private boolean isLeaf(){
return 2*currentIndex + 1 >= binaryTree.length;
}
private int getParent(){
int parentIndex = (currentIndex - 1)/2;
return parentIndex >= 0? parentIndex : 0;
}
private int getNotVisitedChild(){
for(int i = 1; i <= 2; ++){
int childIndex = 2*currentIndex + i;
if(!visited[childIndex ]){
return childIndex;
}
}
return -1;
}
}
__author__ = 'rohanmathure'
from Tree import Tree
from NodeParent import Node
import unittest
class TreeIterator:
def __init__(self):
self.__tree__ = Tree()
self.__currentNode__ = Node()
self.__isFirst = True
def setTree(self,tree):
self.__tree__=tree
def next(self):
tempNode=Node()
if self.__tree__ == None:
return False
if self.__tree__.getRoot() == None:
return False
if self.__isFirst:
self.__isFirst = False
if not self.__tree__.getRoot().getLeft() == None:
self.__currentNode__ = self.getLeftMostChild(self.__tree__.getRoot().getLeft())
else:
self.__currentNode__ = self.__tree__.getRoot()
else:
if not self.__currentNode__.getRight() == None:
self.__currentNode__=self.getLeftMostChild(self.__currentNode__.getRight())
elif self.__currentNode__.getParent() == None:
return False
elif self.__currentNode__ == self.__currentNode__.getParent().getLeft():
self.__currentNode__ = self.__currentNode__.getParent()
elif self.__currentNode__ == self.__currentNode__.getParent().getRight():
tempNode=self.__currentNode__
while not tempNode == None:
if tempNode == tempNode.getParent().getLeft():
self.__currentNode__ = tempNode.getParent()
return self.__currentNode__
else:
tempNode = tempNode.getParent()
else:
return False
return self.__currentNode__
def getLeftMostChild(self,node):
if not node.getLeft() == None:
return self.getLeftMostChild(node.getLeft())
else:
return node
class TestTreeIterator(unittest.TestCase):
def setUp(self):
self.treeIterator=TreeIterator()
tree=Tree()
node1=Node()
node2=Node()
node3=Node()
node4=Node()
node5=Node()
node6=Node()
node7=Node()
node8=Node()
node9=Node()
node12=Node()
node2.setValue(2)
node3.setValue(3)
node1.setValue(1)
node4.setValue(4)
node5.setValue(5)
node6.setValue(6)
node7.setValue(7)
node8.setValue(8)
node9.setValue(9)
node12.setValue(12)
tree.setRoot(node12)
node12.setLeft(node1)
node12.setRight(node9)
node9.setLeft(node2)
node9.setRight(node4)
node2.setRight(node8)
node8.setLeft(node5)
node8.setRight(node6)
node4.setLeft(node3)
node4.setRight(node7)
node3.setParent(node4)
node7.setParent(node4)
node4.setParent(node9)
node9.setParent(node12)
node1.setParent(node12)
node2.setParent(node9)
node8.setParent(node2)
node5.setParent(node8)
node6.setParent(node8)
self.treeIterator.setTree(tree)
def testIteration(self):
self.assertEqual(self.treeIterator.next().getValue(), 1)
self.assertEqual(self.treeIterator.next().getValue(), 12)
self.assertEqual(self.treeIterator.next().getValue(), 2)
self.assertEqual(self.treeIterator.next().getValue(), 5)
self.assertEqual(self.treeIterator.next().getValue(), 8)
self.assertEqual(self.treeIterator.next().getValue(), 6)
self.assertEqual(self.treeIterator.next().getValue(), 9)
self.assertEqual(self.treeIterator.next().getValue(), 3)
self.assertEqual(self.treeIterator.next().getValue(), 4)
self.assertEqual(self.treeIterator.next().getValue(), 7)
__author__ = 'rohanmathure'
from Tree import Tree
from NodeParent import Node
import unittest
class TreeIterator:
def __init__(self):
self.__tree__ = Tree()
self.__currentNode__ = Node()
self.__isFirst = True
def setTree(self,tree):
self.__tree__=tree
def next(self):
tempNode=Node()
if self.__tree__ == None:
return False
if self.__tree__.getRoot() == None:
return False
if self.__isFirst:
self.__isFirst = False
if not self.__tree__.getRoot().getLeft() == None:
self.__currentNode__ = self.getLeftMostChild(self.__tree__.getRoot().getLeft())
else:
self.__currentNode__ = self.__tree__.getRoot()
else:
if not self.__currentNode__.getRight() == None:
self.__currentNode__=self.getLeftMostChild(self.__currentNode__.getRight())
elif self.__currentNode__.getParent() == None:
return False
elif self.__currentNode__ == self.__currentNode__.getParent().getLeft():
self.__currentNode__ = self.__currentNode__.getParent()
elif self.__currentNode__ == self.__currentNode__.getParent().getRight():
tempNode=self.__currentNode__
while not tempNode == None:
if tempNode == tempNode.getParent().getLeft():
self.__currentNode__ = tempNode.getParent()
return self.__currentNode__
else:
tempNode = tempNode.getParent()
else:
return False
return self.__currentNode__
def getLeftMostChild(self,node):
if not node.getLeft() == None:
return self.getLeftMostChild(node.getLeft())
else:
return node
class TestTreeIterator(unittest.TestCase):
def setUp(self):
self.treeIterator=TreeIterator()
tree=Tree()
node1=Node()
node2=Node()
node3=Node()
node4=Node()
node5=Node()
node6=Node()
node7=Node()
node8=Node()
node9=Node()
node12=Node()
node2.setValue(2)
node3.setValue(3)
node1.setValue(1)
node4.setValue(4)
node5.setValue(5)
node6.setValue(6)
node7.setValue(7)
node8.setValue(8)
node9.setValue(9)
node12.setValue(12)
tree.setRoot(node12)
node12.setLeft(node1)
node12.setRight(node9)
node9.setLeft(node2)
node9.setRight(node4)
node2.setRight(node8)
node8.setLeft(node5)
node8.setRight(node6)
node4.setLeft(node3)
node4.setRight(node7)
node3.setParent(node4)
node7.setParent(node4)
node4.setParent(node9)
node9.setParent(node12)
node1.setParent(node12)
node2.setParent(node9)
node8.setParent(node2)
node5.setParent(node8)
node6.setParent(node8)
self.treeIterator.setTree(tree)
def testIteration(self):
self.assertEqual(self.treeIterator.next().getValue(), 1)
self.assertEqual(self.treeIterator.next().getValue(), 12)
self.assertEqual(self.treeIterator.next().getValue(), 2)
self.assertEqual(self.treeIterator.next().getValue(), 5)
self.assertEqual(self.treeIterator.next().getValue(), 8)
self.assertEqual(self.treeIterator.next().getValue(), 6)
self.assertEqual(self.treeIterator.next().getValue(), 9)
self.assertEqual(self.treeIterator.next().getValue(), 3)
self.assertEqual(self.treeIterator.next().getValue(), 4)
self.assertEqual(self.treeIterator.next().getValue(), 7)
__author__ = 'rohanmathure'
from Tree import Tree
from NodeParent import Node
import unittest
class TreeIterator:
def __init__(self):
self.__tree__ = Tree()
self.__currentNode__ = Node()
self.__isFirst = True
def setTree(self,tree):
self.__tree__=tree
def next(self):
tempNode=Node()
if self.__tree__ == None:
return False
if self.__tree__.getRoot() == None:
return False
if self.__isFirst:
self.__isFirst = False
if not self.__tree__.getRoot().getLeft() == None:
self.__currentNode__ = self.getLeftMostChild(self.__tree__.getRoot().getLeft())
else:
self.__currentNode__ = self.__tree__.getRoot()
else:
if not self.__currentNode__.getRight() == None:
self.__currentNode__=self.getLeftMostChild(self.__currentNode__.getRight())
elif self.__currentNode__.getParent() == None:
return False
elif self.__currentNode__ == self.__currentNode__.getParent().getLeft():
self.__currentNode__ = self.__currentNode__.getParent()
elif self.__currentNode__ == self.__currentNode__.getParent().getRight():
tempNode=self.__currentNode__
while not tempNode == None:
if tempNode == tempNode.getParent().getLeft():
self.__currentNode__ = tempNode.getParent()
return self.__currentNode__
else:
tempNode = tempNode.getParent()
else:
return False
return self.__currentNode__
def getLeftMostChild(self,node):
if not node.getLeft() == None:
return self.getLeftMostChild(node.getLeft())
else:
return node
class TestTreeIterator(unittest.TestCase):
def setUp(self):
self.treeIterator=TreeIterator()
tree=Tree()
node1=Node()
node2=Node()
node3=Node()
node4=Node()
node5=Node()
node6=Node()
node7=Node()
node8=Node()
node9=Node()
node12=Node()
node2.setValue(2)
node3.setValue(3)
node1.setValue(1)
node4.setValue(4)
node5.setValue(5)
node6.setValue(6)
node7.setValue(7)
node8.setValue(8)
node9.setValue(9)
node12.setValue(12)
tree.setRoot(node12)
node12.setLeft(node1)
node12.setRight(node9)
node9.setLeft(node2)
node9.setRight(node4)
node2.setRight(node8)
node8.setLeft(node5)
node8.setRight(node6)
node4.setLeft(node3)
node4.setRight(node7)
node3.setParent(node4)
node7.setParent(node4)
node4.setParent(node9)
node9.setParent(node12)
node1.setParent(node12)
node2.setParent(node9)
node8.setParent(node2)
node5.setParent(node8)
node6.setParent(node8)
self.treeIterator.setTree(tree)
def testIteration(self):
self.assertEqual(self.treeIterator.next().getValue(), 1)
self.assertEqual(self.treeIterator.next().getValue(), 12)
self.assertEqual(self.treeIterator.next().getValue(), 2)
self.assertEqual(self.treeIterator.next().getValue(), 5)
self.assertEqual(self.treeIterator.next().getValue(), 8)
self.assertEqual(self.treeIterator.next().getValue(), 6)
self.assertEqual(self.treeIterator.next().getValue(), 9)
self.assertEqual(self.treeIterator.next().getValue(), 3)
self.assertEqual(self.treeIterator.next().getValue(), 4)
self.assertEqual(self.treeIterator.next().getValue(), 7)
Ruby impl. Using stack to capture stack-frames of depth-first search. Running time: O(|V|+|E|). Space: O(|V|).
require 'tree'
require 'ds'
root_node = Tree::TreeNode.new("1", 1)
child1 = Tree::TreeNode.new("2",2)
child2 = Tree::TreeNode.new("3",3)
grandchild1=Tree::TreeNode.new("4",4)
grandchild2=Tree::TreeNode.new("5",5)
grandchild3=Tree::TreeNode.new("6",6)
grandchild4=Tree::TreeNode.new("7",7)
child1 << grandchild1
child1 << grandchild2
child2 << grandchild3
child2 << grandchild4
root_node << child1
root_node << child2
root_node.print_tree
module Iterator
def next
nil
end
def has_next?
false
end
end
class TreeIterator
include Iterator
def initialize(root_node)
@stack=DS::Stack.new
@stack.push(root_node)
end
def next
node = @stack.pop
node.children.each do |child|
@stack.push(child)
end
node
end
def has_next?
!@stack.empty?
end
end
class MyTree
def initialize(root_node)
@root_node=root_node
end
def iterator
TreeIterator.new(@root_node)
end
end
iterator = MyTree.new(root_node).iterator
while iterator.has_next?
print "#{iterator.next.name}"
print ' -> ' if iterator.has_next?
end
Output:
* 1
|---+ 2
| |---> 4
| +---> 5
+---+ 3
|---> 6
+---> 7
1 -> 3 -> 7 -> 6 -> 2 -> 5 -> 4
Java implementation that does non-recursive in-order traversal using a stack.
public class TreeIterator implements Iterator<TreeNode> {
Stack<TreeNode> inorder = new Stack<>();
public TreeIterator(TreeNode node) {
goAsLeftAsPossible(node);
}
public void inorderTraversal() {
goAsLeftAsPossible(inorder.pop().right);
}
private void goAsLeftAsPossible(TreeNode node) {
while (node != null) {
inorder.push(node);
node = node.left;
}
}
@Override
public boolean hasNext() {
return !inorder.isEmpty();
}
@Override
public TreeNode next() {
if (!hasNext()) {
throw new IllegalStateException();
}
TreeNode next = inorder.peek();
inorderTraversal();
return next;
}
}
Inorder traversal
public static void main(String args[])
{
Node c = new Node(1,new Node(2, new Node(3, null, new Node(4, null, null)), new Node(5, new Node(6, null, null), new Node(7, null, null))), new Node(8, null, null));
It it = new It(c);
while (it.hasNext()) {
Node next = it.next();
System.out.println(Integer.toString(next.value));
}
}
public static class It {
Stack<Node> s;
Node current;
public It(Node n) {
s = new Stack<Node>();
current = n;
while (current.left != null) {
s.push(current);
current = current.left;
}
}
public Node next() {
Node result = current;
if (current.right != null) {
s.push(current);
current = current.right;
while (current.left != null) {
s.push(current);
current = current.left;
}
} else {
while(s.size() > 0 && current == s.peek().right) {
current = s.pop();
}
if (s.size() == 0) {
current = null;
} else {
current = s.pop();
}
}
return result;
}
public boolean hasNext() {
return current != null;
}
}
public static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
Performing action on the given (processing\visiting) node is denoted as "D". And traversing left child node denoted with "L" and right child node denoted with "R". So, there are three possible ways one can traverse the tree.
1. Preorder (DLR) traversal
2. Inorder (LDR) traversal
3. Postorder (LRD) traversal
All of them are O(n) complexity and O(n) space complexity. No major difference between them except the sequence of the actions. All of them can be achieved using either recursive or non-recursive method. Here is one of the implementation using PreOrder Traversal with recursive method.
struct Node {
int data;
struct Node *left;
struct Node *right;
};
//
// Pre-Order Traversal method (DLR)
// i.e. 1. Visit the root 2. Traverse Left subtree 3. Traverse the right subtree
//
void BinaryTreeTraversal(struct Node *root)
{
if (root) // make sure the node is not NULL, that is the recursive terminator
{
printf("%d ", root->data);
BinaryTreeTraversal(root->left);
BinaryTreeTraversal(root->right);
}
}
But you did not implement an iterator.
They are probably asking for a lazy iterator, which will require stack based traversal.
Mohan, you are implementing tree traversal. The question asked for an iterator. In Java, for example, that would be a class implementing the Iterator interface (next(), hasNext() and remove() methods).
BFS Iterator
- I.R. July 07, 2015