Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
In case of odd level we have to add an extra condition for printing mid-level -
if(firstLevel==lastLevel)
printLevel(root, firstLevel, true);
C#,
void PrintInwardSpiralTree(TreeNode root)
{
if (root == null)
return;
var list = new List<List<TreeNode>>();
var currentList = new List<TreeNode>();
var nextList = new List<TreeNode>();
currentList.Add(root);
while (currentList.Count > 0)
{
list.Add(currentList);
nextList = new List<TreeNode>();
foreach (var node in currentList)
{
if (node.Left != null)
nextList.Add(node.Left);
if (node.Right != null)
nextList.Add(node.Right);
}
currentList = nextList;
}
int n = list.Count;
int first = 0;
int last = n - 1;
int i = 1;
while (i <= n)
{
if (i % 2 == 1)
{
currentList = list[first];
for (int j = 0; j < currentList.Count; j++)
Console.Write(currentList[j].Value + ", ");
first++;
}
else
{
currentList = list[last];
for (int j = currentList.Count - 1; j >= 0; j--)
Console.Write(currentList[j].Value + ", ");
last--;
}
i++;
}
Console.WriteLine();
}
I propose a two step solution here:
1. Using a Depth First Traversal, push all the elements into a stack(S1) with a stub/delimiter in between each level. This can be achieved with a queue(Q) and stack(S1) as follows:
Push root element into the queue and then push a delimiter/stub value into the queue
While queue not empty:
dequeue next element
if(!delimiter)
push element into stack S1
enqueue its childern into the queue
else //if delimiter
push a delimiter into both stack and queue
2. Using two stacks S1 and S2, pop the levels in the spiral way i.e. pop top level from S1(level 1 of the tree), then pop remaining S1 into S2. Pop first level of S2(level n of binary tree) and pop remaining S2 into S1 and repeat till empty.
Minor variation of another answer already listed. In Java:
void printSpiral(Node root) {
final int height = getHeight(root);
int i;
for (i = 0; i < (height / 2); i++) {
printLevelLeftToRight(i + 1, 1, root);
printLevelRightToLeft(height - i, 1, root);
}
if ((height % 2) == 1) {
printLevelLeftToRight(i + 1, 1, root);
}
System.out.println();
}
void printLevelLeftToRight(final int desiredLevel, int currentLevel, final Node node) {
if (desiredLevel == currentLevel) {
System.out.print(node.data + " ");
return;
}
if (node.left != null) {
printLevelLeftToRight(desiredLevel, currentLevel + 1, node.left);
}
if (node.right != null) {
printLevelLeftToRight(desiredLevel, currentLevel + 1, node.right);
}
}
void printLevelRightToLeft(final int desiredLevel, int currentLevel, final Node node) {
if (desiredLevel == currentLevel) {
System.out.print(node.data + " ");
return;
}
if (node.right != null) {
printLevelRightToLeft(desiredLevel, currentLevel + 1, node.right);
}
if (node.left != null) {
printLevelRightToLeft(desiredLevel, currentLevel + 1, node.left);
}
}
FP implementation in Scala. It is lazily evaluated so it should consume very little memory.
1. transform tree into rows (BFS)
2. generate sequence for traversal and map to rows
case class BTree[+T](left: Option[BTree[T]], right: Option[BTree[T]], value: T)
object SpiralTraversal {
def traverse[T](tree: BTree[T]): Iterator[T] = {
type BT = BTree[T]
def visit(nodes: Stream[BT]): (Stream[T], Stream[BT]) = {
nodes.foldLeft((Stream.empty[T], Stream.empty[BT])) {
case ((outT, outRow), node) =>
val nextRow = Stream(node.left, node.right).flatMap {
case Some(subtree) => Stream(subtree)
case _ => Stream.empty
}
(outT ++ Stream(node.value), outRow ++ nextRow)
}
}
def makeRows(trees: Stream[BT]): List[Stream[T]] = {
if (trees.isEmpty) {
return List.empty
}
val (rowT, nextRow) = visit(trees)
List(rowT) ++ makeRows(nextRow)
}
def comb(n: Int, m: Int): Stream[(Int, Boolean)] =
if (n > m) {
Stream.empty
} else if (n == m) {
Stream((n, false))
} else {
(n, false) #::(m, true) #:: comb(n + 1, m - 1)
}
val rows = makeRows(Stream(tree))
comb(0, rows.size - 1).flatMap {
case (rowNumber, reversed) =>
val row = rows(rowNumber)
if (reversed) row.reverse else row
}.iterator
}
}
void inward(TreeNode* root){
int count = 0;
queue<TreeNode*> q;
vector<vector<int> > result;
if(root != NULL){
count++;
q.push(root);
}
while(count != 0){
int newcount = 0;
vector<int> level;
for(int i = 0; i < count; ++i){
TreeNode* curr = q.front();
q.pop();
level.push(curr->val);
if(curr->left){
newcount++;
q.push(curr->left);
}
if(curr->right){
newcount++;
q.push(curr->right);
}
}
result.push_back(level);
count = newcount;
}
int left = 0, right = result.size() - 1;
while(left <= right){
vector<int> level = result[left++];
for(int i : level){
cout << i << " ";
}
cout << endl;
if(left < right){
level = result[right--];
for(int i = level.size() - 1; i >= 0; i--){
cout << i << " ";
}
cout << endl;
}
}
}
Using the HashMap and Dequeue as the DS
public void printSpiralInwards(Node root){
Map<Integer,ArrayList<Node>> mp = new HashMap<Integer, ArrayList<Node>>();
ArrayList<Node> arrayList = null;
ArrayList<Node> arrayList1 = null;
int i = 0;
if(root == null)
return;
Deque<Node> queue = new LinkedList<Node>();
queue.add(root);
queue.add(null);
while(queue.size()>1){
Node temp = queue.peekFirst();
arrayList = new ArrayList<Node>();
while(temp!=null){
temp = queue.pollFirst();
arrayList.add(temp);
System.out.println(" "+ temp.data );
if(temp.left!=null)
queue.offerLast(temp.left);
if(temp.right!=null)
queue.offerLast(temp.right);
temp = queue.peekFirst();
}
mp.put(i++, arrayList);
temp = queue.peekLast();
arrayList1 = new ArrayList<Node>();
while(temp!=null){
temp = queue.pollLast();
arrayList1.add(temp);
System.out.println(" "+ temp.data );
if(temp.right!=null)
queue.offerFirst(temp.right);
if(temp.left!=null)
queue.offerFirst(temp.left);
temp = queue.peekLast();
}
mp.put(i++, arrayList1);
}
Deque<ArrayList<Node>> de = new LinkedList<ArrayList<Node>>();
de.addAll(mp.values());
while(!de.isEmpty()){
System.out.println(" ");
ArrayList<Node> first = de.pollFirst();
Iterator<Node> itr = first.iterator();
while(itr.hasNext()){
System.out.print(" "+itr.next().data);
}
System.out.println(" ");
ArrayList<Node> sec = de.pollLast();
Iterator<Node> itr1 = sec.iterator();
while(itr1.hasNext()){
System.out.print(" "+itr1.next().data);
}
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
public class SpiralTree {
static int getHeight(Node root) {
if (root == null) {
return 0;
}
return 1 + Math.max(getHeight(root.getLeft()), getHeight(root.getRight()));
}
static void printSpiral(Node root) {
if (root == null) {
return;
}
List<Node> nodesList = Arrays.asList(root);
Queue<List<Integer>> queue = new LinkedList<>();
Stack<List<Integer>> stack = new Stack<>();
populateStackNQueue(nodesList, queue, stack, 1, getHeight(root));
while (true) {
if (queue.isEmpty() && stack.isEmpty()) {
break;
}
if (!queue.isEmpty()) {
List<Integer> valuesList = queue.poll();
for (Integer value : valuesList) {
System.out.print(" " + value);
}
}
if (!stack.isEmpty()) {
List<Integer> valuesList = stack.pop();
for (int i = valuesList.size()-1; i >= 0; i--) {
System.out.print(" " + valuesList.get(i));
}
}
}
}
static void populateStackNQueue(List<Node> nodesList, Queue<List<Integer>> queue, Stack<List<Integer>> stack,
int level, int height) {
if (nodesList.size() == 0) {
return;
}
List<Node> childNodesList = new ArrayList<>();
List<Integer> valuesList = new ArrayList<>(nodesList.size());
for (Node node : nodesList) {
valuesList.add(node.getValue());
if (node.getLeft() != null) {
childNodesList.add(node.getLeft());
}
if (node.getRight() != null) {
childNodesList.add(node.getRight());
}
}
if (level <= ((height + 1) / 2)) {
queue.add(valuesList);
} else {
stack.add(valuesList);
}
populateStackNQueue(childNodesList, queue, stack, level + 1, height);
}
public static void main(String[] args) {
Node root = new Node(1,
new Node(2, new Node(4, new Node(8), new Node(9)), new Node(5, new Node(10), new Node(11))),
new Node(3, new Node(6, new Node(12), new Node(13)), new Node(7, new Node(14), new Node(15))));
printSpiral(root);
}
}
class Node {
private int value;
private Node left;
private Node right;
public Node(int value) {
super();
this.value = value;
}
public Node(int value, Node left, Node right) {
super();
this.value = value;
this.left = left;
this.right = right;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
- abhay0609 December 10, 2015