Amazon Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
cleaner version
public class ZigZagfs {
Node root = null;
Map<Integer, Node> nodes = new HashMap<Integer,Node>();
static class Node {
int value;
Node left;
Node right;
public Node ( int value ){
this.value = value;
}
public String toString(){
return ""+this.value;
}
}
public ZigZagfs(String fileName) {
try (BufferedReader rdr = new BufferedReader(new FileReader(fileName))) {
String line = null;
while ((line = rdr.readLine()) != null) {
Node n = parseLine(line);
if ( root == null ) root = n;
}
}
catch (IOException ioe) {
System.err.println("error: " + ioe);
}
}
Node parseNode( String str ) {
if ( str == null ) return null;
str = str.trim();
if ( str.length() == 0 ) return null;
int val = Integer.parseInt(str);
if ( nodes.containsKey(val) ) return nodes.get(val);
Node n = new Node(val);
nodes.put(val, n);
return n;
}
Node parseLine(String line) {
int idx = line.indexOf(":");
Node n = parseNode( line.substring(0, idx) );
String[] children = line.substring(idx + 1).split(",");
if ( children.length > 0 ) n.left = parseNode(children[0]);
if ( children.length > 1 ) n.right = parseNode(children[1]);
System.out.println(n.value + ": " + n.left + "," + n.right);
return n;
}
void print() {
Node node = root;
Deque<Node> q1 = new LinkedList<Node>();
q1.add(node);
Queue<Node> q2 = new LinkedList<Node>();
String comma = "";
while (!q1.isEmpty() || !q2.isEmpty()) {
while (!q1.isEmpty()) {
node = q1.removeLast();
System.out.print(comma + node.value);
if (node.left != null)
q2.add(node.left);
if (node.right != null)
q2.add(node.right);
comma = ",";
}
System.out.println("");
comma = "";
while (!q2.isEmpty()) {
node = q2.remove();
System.out.print(comma + node.value);
if (node.left != null)
q1.add(node.left);
if (node.right != null)
q1.add(node.right);
comma = ",";
}
System.out.println("");
comma = "";
}
}
static public void main(String[] args) {
ZigZagfs zigZag = new ZigZagfs(args[0]);
zigZag.print();
}
}
//Use 2 stacks O(n) time O(2^h) space (if we have a perfect binary tree).
public class Node
{
private int value;
private Node left;
private Node right;
}
public class ZigZagService
{
public void zigZagTraverse(Node n)
{
if(n==null)
{
System.out.println("error input tree is null");
}
Stack<Node> lr=new Stack<Node>();//will be used to print nodes in left to right order
Stack<Node> rl=new Stack<Node>();//will be used to print nodes in right to left order
rl.push(n);
while(true)
{
if(rl.isEmpty()&&lr.isEmpty())
{
break;
}
while(!rl.isEmpty())
{
Node top=rl.pop();
System.out.print(top.value());
if(top.right!=null)
{
lr.push(top.right);
}
if(top.left!=null)
{
lr.push(top.left);
}
}
while(!lr.isEmpty())
{
Node top=lr.pop();
System.out.print(top.value);
if(top.left!=null)
{
rl.push(top.left);
}
if(top.right!=null)
{
rl.push(top.right);
}
}
}
}
}
}
//Use two stacks O(n) time and O(2^h) space if we have a perfect tree
public class Node
{
private int value;
private Node left;
private Node right;
}
public class ZigZagService
{
public void ZigZagTraverse(Node n)
{
if(n==null)
{
System.out.println("error input is null");
}
Stack<Node> lr=new Stack<Node>();//Will print nodes from left to right
Stack<Node> rl=new Stack<Node>();//Will print nodes from right to left
rl.push(n);
while(true)
{
if(lr.isEmpty() && rl.isEmpty())
{
break;
}
while(!lr.isEmpty())
{
Node x=lr.pop();
System.out.print(x.value);
if(x.left!=null)
{
rl.push(x.left);
}
if(x.right!=null)
{
rl.push(x.right);
}
}
while(!rl.isEmpty())
{
Node x=rl.pop();
System.out.print(x.value);
if(x.right!=null)
{
lr.push(x.right);
}
if(x.left!=null)
{
lr.push(x.left);
}
}
}
}
void zigZagTraverse(Node n) {
var leftToRight = new Stack<Node>();
var rightToLeft = new Stack<Node>();
if (n == null)
return;
rightToLeft.Push(n);
visitRightToLeft(n, leftToRight, rightToLeft);
}
private void visitLeftToRight(Stack<Node> leftToRight, Stack<Node> rightToLeft) {
while (leftToRight.Peek() != null) {
var nn = leftToRight.Pop();
print n;
if (n.Left != null)
rightToLeft.Push(n.Left);
if (n.Right != null)
rightToLeft.Push(n.Right);
}
if (rightToLeft.Peek() != null)
visitRightToLeft(n, leftToRight, rightToLeft);
}
private void visitRightToLeft(Stack<Node> leftToRight, Stack<Node> rightToLeft) {
while (rightToLeft.Peek() != null) {
var n = rightToLeft.Pop();
print n;
if (n.Right != null)
leftToRight.Push(n.Right);
if (n.Left != null)
leftToRight.Push(n.Left);
}
if (leftToRight.Peek() != null)
visitLeftToRight(n, leftToRight, rightToLeft);
}
class BinaryTree<K>{
private class Node{
K value;
Node left;
Node right;
Node(K val){
value = val;
left = null;
right = null;
}
}
/* Queue/Stack Implementation */
private class Queue{
private class NodeQ{
Node valNode;
NodeQ next;
NodeQ(Node val){
this.valNode = val;
}
}
private NodeQ HEAD = null;
private NodeQ TAIL = null;
private void enque(Node val){
if(val == null) return;
NodeQ nodeq = new NodeQ(val);
if(TAIL == null){
TAIL = nodeq;
HEAD = nodeq;
}
else{
TAIL.next = nodeq;
TAIL = nodeq;
}
}
private void push(Node val){
if(val == null) return;
NodeQ nodeq = new NodeQ(val);
if(HEAD == null){//empty queue
HEAD = nodeq;
TAIL = nodeq;
}
else{
nodeq.next = HEAD;
HEAD = nodeq;
}
}
private Node deque(){
if(HEAD == null)
return null;
Node retNode = HEAD.valNode;
HEAD = HEAD.next;
if(HEAD == null)
TAIL = null;//queue is empty
return retNode;
}
private boolean isEmpty(){
return (HEAD == null);
}
}
/* End of Queue implementation*/
private Node root;
/* Fill method in horizontal manner*/
public void put(K val){
Node node = new Node(val);
if(root == null){
root = node;
return;
}
Node rt = root;
Queue q = new Queue();
q.enque(rt);
while(!q.isEmpty()){
Node popped = q.deque();
if(popped.left == null){
popped.left = node;
return;
}
else
q.enque(popped.left);
if(popped.right == null){
popped.right = node;
return;
}
else
q.enque(popped.right);
}
}
/* In order traverse*/
public void inOrdertraverse(){
traverseIn(root);
}
private void traverseIn(Node r){
if(r == null) return;
traverseIn(r.left);
System.out.println(r.value);
traverseIn(r.right);
}
public void horizontalTraverse(){
Node rt = root;
Queue q = new Queue();
q.enque(rt);
while(!q.isEmpty()){
Node popped = q.deque();
System.out.println(popped.value);
if(popped.left != null){
q.enque(popped.left);
}
if(popped.right != null){
q.enque(popped.right);
}
}
}
public void zigzagTx(){
Queue queue = new Queue();
Node rt = root;
queue.enque(rt);
if(rt!= null)
System.out.println(rt.value);
boolean toggled = false;
while(true){
Queue Q1 = new Queue();//to carry fwd the process
Queue Q2 = new Queue();//for prints
while(!queue.isEmpty()){
Node x = queue.deque();
if(x.left != null){
Q1.enque(x.left);
if(!toggled)
Q2.enque(x.left);
else
Q2.push(x.left);
}
if(x.right != null){
Q1.enque(x.right);
if(!toggled)
Q2.enque(x.right);
else
Q2.push(x.right);
}
}
if(Q1.isEmpty()) break;
queue = Q1;
while(!Q2.isEmpty()){
System.out.println(Q2.deque().value);
}
if(toggled)
toggled = false;
else
toggled = true;
}
}
}
public static class TreeNode<T>
{
TreeNode(T value, TreeNode left, TreeNode right)
{
this.value = value;
this.left = left;
this.right = right;
}
T value;
TreeNode left;
TreeNode right;
@Override
public String toString()
{
return value.toString();
}
}
public static void printZigZagTree( TreeNode head )
{
List<TreeNode> buffer = new ArrayList<TreeNode>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(head);
//add the 'dummy' node:
queue.add( new TreeNode(null, null, null) );
boolean isLeftToRight =
//true;
false;
while( ! queue.isEmpty() )
{
TreeNode node = queue.poll();
if(node.value == null) //if this is dummy, we know that it is a new "level" in the tree. so handle the previous level (in the buffer)...
{
if(isLeftToRight)
{
for(TreeNode tn : buffer)
{
System.out.print(tn);
}
}
else
{
for(int i = buffer.size()-1; i >= 0 ; --i)
{
System.out.print(buffer.get(i));
}
}
System.out.println();
buffer.clear();
isLeftToRight = !isLeftToRight;
//add the dummy only if the Q is not empty - o/w we run into endless loop:
if(!queue.isEmpty())
queue.add(node);
}
else
{
buffer.add(node);
//add its child to queue:
if(node.left != null)
queue.add(node.left);
if(node.right != null)
queue.add(node.right);
}
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
helper(res,1,root);
return res;
}
public void helper(List<List<Integer>> list,int level,TreeNode root){
if(root==null) return;
if(list.size()<level){
List<Integer> items=new ArrayList<Integer>();
items.add(root.val);
list.add(items);
}else{
if(level%2!=0) list.get(level-1).add(root.val);
else list.get(level-1).add(0,root.val);
}
helper(list,level+1,root.left);
helper(list,level+1,root.right);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
helper(res,1,root);
return res;
}
public void helper(List<List<Integer>> list,int level,TreeNode root){
if(root==null) return;
if(list.size()<level){
List<Integer> items=new ArrayList<Integer>();
items.add(root.val);
list.add(items);
}else{
if(level%2!=0) list.get(level-1).add(root.val);
else list.get(level-1).add(0,root.val);
}
helper(list,level+1,root.left);
helper(list,level+1,root.right);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
helper(res,1,root);
return res;
}
public void helper(List<List<Integer>> list,int level,TreeNode root){
if(root==null) return;
if(list.size()<level){
List<Integer> items=new ArrayList<Integer>();
items.add(root.val);
list.add(items);
}else{
if(level%2!=0) list.get(level-1).add(root.val);
else list.get(level-1).add(0,root.val);
}
helper(list,level+1,root.left);
helper(list,level+1,root.right);
}
}
Notice that this problem is very similar to the lever-order tree traversal. This problem can be implemented by a queue.
The only difference is that while in odd levels we traverse left to right in the even layers me traverse right to left. We will traverse the the tree while keeping track of even/odd layer. This will affect the order we put the nodes on the queue.
Your answer is not right.
0 will add 1,2 into the queue
then 1 will add 4, 3 into the queue
and 2 will add 6, 5 into the queue
it will look like 0, 1, 2, 4, 3, 6, 5
This can be done with a BFS traversal of the tree. O(n) complexity and O(n) memory:
- zortlord July 16, 2015