Amazon Interview Question
Senior Software Development EngineersTeam: Amazon Digital Ad
Country: United States
Interview Type: Phone Interview
This is an Objective-C solution O(n) time and O(n) extra space using a queue and stack and traverse the tree by level.
-(void)getLevelOrderTraversalReverse:(TreeNode *)root{
if(root == nil){
return;
}
NSMutableArray *queue = [NSMutableArray new];
NSMutableArray *stack = [NSMutableArray new];
NSMutableString *result = [[NSMutableString alloc] init];
[queue addObject:root];
while ([queue count] > 0) {
root = [queue objectAtIndex:0];
[queue removeObjectAtIndex:0];
if(root.rigth != nil){
root.rigth.level = root.level + 1;
[queue addObject:root.rigth];
}
if(root.left != nil){
root.left.level = root.level + 1;
[queue addObject:root.left];
}
[stack addObject:root];
}
while([stack count] > 0){
root = [stack lastObject];
[stack removeLastObject];
[result appendString:[NSString stringWithFormat:@"%i ", root.value]];
}
NSLog(@"\n\nBy Level Reverse: %@\n", result);
}
gekko is correct, it is meaningless. But..
In any case, given this json :
{
"value" : 1 , "children" : [
{ "value" : 2 , "children" : [
{ "value" : 4 , "children" : [] },
{ "value" : 5 , "children" : [] }
] } ,
{ "value" : 3 , "children" : [
{ "value" : 6 , "children" : [] },
{ "value" : 7 , "children" : [] }
] }
]
}
This code is going to work out well for the reverse God knows what level order thing:
/*
A Level order traversal.
The key is to understand that,
you need to maintain two queues, one for current,
another for next level.
After a level is exhausted,
one needs to replace that queue by the one from built up.
As we can see, this won't solve Amazon's problem,
Which is a reverse level order traversal.
So, we need to use a stack to store the per level nodes
which are to be stored in a queue! Thus,
The solution becomes , storing the queue in a stack!
But then, who needs queues? We can simply use a list!
*/
def reverse_level_order( root ){
cur = list( root ) // current level
stack = list() ; stack.push( list( cur ) )
while ( !empty(cur) ){
next = list()
for ( node : cur ){
for ( child : node.children ){
next += child
}
}
// push the level into the stack
stack.push ( list( next) )
cur = next
}
// now unwind the stack
while ( !empty(stack) ){
level = stack.pop()
for ( node : level ){
printf( ' %s ' , node.value )
}
}
println()
}
// call it
reverse_level_order( json( 'tree.json' ,true ) )
I am using imperative paradigm - to ensure that it stays comprehensible.
This is a reverse level order traversal problem. Modify the level order traversal code , insert a statement to insert the data into the stack where you would normally print the data. After you visited all the nodes. Now pop everything from stack, as you pop and print you should see node's data printed in reverse level order traversal.
some one down voted my answer, can you explain why this is not correct
func PrintByLevel(root *TreeNode) {
data := [][]int{}
_ByLevel(root, 0, &data)
for i:= len(data) - 1; i >= 0; i-- {
for _, v := range data[i] {
fmt.Print(v)
}
}
}
func _ByLevel(root *TreeNode, level int, data *[][]int) {
if root == nil {
return
}
if len(*data) <= level {
*data = append(*data, []int{})
}
(*data)[level] = append((*data)[level], root.val)
_ByLevel(root.left, level + 1, data)
_ByLevel(root.right, level + 1, data)
}
This can be solved either using iterative breadth or recursive depth first search.
// breadth first approach, O(N)
private static Stack<LinkedList<TreeNode>> createLevelLinkedListBFS(TreeNode root) {
Stack<LinkedList<TreeNode>> result = new Stack<>();
LinkedList<TreeNode> workingTree = new LinkedList<>();
workingTree.add(root);
while (!workingTree.isEmpty()) {
result.add(workingTree);
LinkedList<TreeNode> levelNodes = workingTree;
workingTree = new LinkedList<>();
for (TreeNode node : levelNodes) {
if (node.left != null) {
workingTree.add(node.left);
}
if (node.right != null) {
workingTree.add(node.right);
}
}
}
return result;
}
// depth first approach, O(N)
private static Stack<LinkedList<TreeNode>> createLevelLinkedListDFS(TreeNode root) {
ArrayList<LinkedList<TreeNode>> levelsList = new ArrayList<>();
createLevelLinkedListDFS(root, levelsList, 0);
Stack<LinkedList<TreeNode>> result = new Stack<>();
for (LinkedList<TreeNode> nodes : levelsList) {
result.push(nodes);
}
return result;
}
private static void createLevelLinkedListDFS(TreeNode root, ArrayList<LinkedList<TreeNode>> result, int level) {
if (result.size() == level) {
result.add(new LinkedList<>());
}
LinkedList<TreeNode> nodes = result.get(level);
nodes.add(root);
if (root.left != null) {
createLevelLinkedListDFS(root.left, result, level + 1);
}
if (root.right != null) {
createLevelLinkedListDFS(root.right, result, level + 1);
}
}
BFS in largest first order, and then reverse the result:
public static String bottomsUp(Node root){
StringBuilder sb = new StringBuilder();
Queue<Node> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()) {
Node n = q.poll();
sb.append(n.value);
if (n.right != null) {
q.add(n.right);
}
if (n.left != null) {
q.add(n.left);
}
}
return sb.reverse().toString();
}
Here's the solution in Python.
Traverse the tree with breadth-first search, going right to left, and add the values to a list.
Reverse the values in the list to get a reverse breadth-first search, going left to right.
root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
from collections import deque
queue = deque([root])
values = []
while queue:
node = queue.popleft()
if node.right is not None:
queue.append(node.right)
if node.left is not None:
queue.append(node.left)
values.append(node.value)
# print the values in reverse
print(''.join([str(i) for i in values[::-1]]))
static int mid=0;
public void level_order_tree(node root,int i){
stack = new node[size+1];
if(mid == 0 && root != null){
stack[mid] = root;
mid++;
}
while(root != null){
if(root.left != null && root.right !=null){
stack[mid] = root.right;
mid++;
stack[mid] = root.left;
mid++;
root = stack[i];
i++;
}else if(root.left != null && root.right == null){
stack[mid] = root.left;
mid++;
root = stack[i];
i++;
}else if(root.right != null && root.left == null){
stack[mid] = root.right;
mid++;
root = stack[i];
i++;
}else{
root = stack[i];
i++;
}
}
for(int j = mid-1;j>=0;j--){
System.out.print(stack[j].data);
}}
Use BFS with two stacks, that will do it!
bfsModTraversal(Node root){
Stack<Node> visitStack = new Stack<Node>();
Stack<Node> traversalStack = new Stack<Node>();
visitedStack.push(root);
while(!visitStack.isEmpty()) {
Node curr = visistStack.pop();
traversalStack.push(curr);
for(Node var in curr.children)
visistStack.push(var);
}
while(!traversalStack.isEmpty()) {
System.out.println(traversalStack.pop().data);
}
}
#include "stdafx.h"
#include <boost/core/is_same.hpp>
#include <boost/core/demangle.hpp>
#include <typeinfo>
#include <unordered_set>
#include <vector>
#include <thread>
#include <future>
#include <numeric>
#include <iostream>
#include <chrono>
#include <algorithm>
#include <utility>
#include <atomic>
using std::unordered_set;
using namespace std;
struct node
{
int data;
node* left;
node* right;
node() :left(nullptr), right(nullptr) {}
};
void PrintByLevel(node * root,
std::vector <std::vector < int>> &v,
int level)
{
if (root == nullptr) return;
if (level >= v.size()) v.push_back({});
v[level].push_back(root->data);
++level;
PrintByLevel(root->left, v, level);
PrintByLevel(root->right, v, level);
}
void LevelOrder(node * root)
{
if (root == nullptr) return;
std::vector <std::vector < int> > v(1);
PrintByLevel(root,
v,
0);
for (auto & line : v)
for (auto & i : line)
cout << i << " ";
}
void LevelBackOrder(node * root)
{
if (root == nullptr) return;
std::vector <std::vector < int> > v(1);
PrintByLevel(root,
v,
0);
for (auto rit = v.rbegin(); rit != v.rend(); ++rit)
{
for (auto &it : *rit)
cout << it;
}
/*
for (auto rit = v.rbegin(); rit != v.rend; ++rit)
for (int i = *rit[0]; i < )
cout << *rit << " ";
*/
}
int main()
{
node * root = new node();
root->data = 1;
node * leftNode = new node();
leftNode->data = 2;
node * rightNode = new node();
rightNode->data = 3;
root->left = leftNode;
root->right = rightNode;
node * leftleftNode = new node();
leftleftNode->data = 4;
node * leftrightNode = new node();
leftrightNode->data = 5;
leftNode->left = leftleftNode;
leftNode->right = leftrightNode;
node * rightleftNode = new node();
rightleftNode->data = 6;
rightNode->right = rightleftNode;
node * leftrightNode3 = new node();
leftrightNode3->data = 7;
leftrightNode->left = leftrightNode3;
//LevelOrder(root);
LevelBackOrder(root);
//
/*
1
2 3
4 5 6
7
*/
}
public void void printTreeLevelFromBottom(Node root) {
Queue<Node> queue = new LinkedList<>();
List<Integer> printTreeList = new ArrayList<>();
printTreeList.add(root.data);
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
Node leftNode = node.left;
Node rightNode = node.right;
if (rightNode != null) {
printTreeList.add(rightNode.data);
queue.add(rightNode);
}
if (leftNode != null) {
printTreeList.add(leftNode.data);
queue.add(leftNode);
}
}
for (int index = printTreeList.size() - 1; index >= 0; index--) {
System.out.print(printTreeList.get(index) + " ");
}
}
public void void printTreeLevelFromBottom(Node root) {
Queue<Node> queue = new LinkedList<>();
List<Integer> printTreeList = new ArrayList<>();
printTreeList.add(root.data);
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
Node leftNode = node.left;
Node rightNode = node.right;
if (rightNode != null) {
printTreeList.add(rightNode.data);
queue.add(rightNode);
}
if (leftNode != null) {
printTreeList.add(leftNode.data);
queue.add(leftNode);
}
}
for (int index = printTreeList.size() - 1; index >= 0; index--) {
System.out.print(printTreeList.get(index) + " ");
}
}
Solution with O(N) time and O(1) memory (modifying tree):
Let's convert binary tree into a linked list where a right link points to the next element. And print all elements in a linked list.
import java.io.*;
import java.util.*;
public class Main {
static class TreeNode {
int x;
TreeNode left;
TreeNode right;
public TreeNode(int x) {
this.x = x;
}
}
static class Result {
TreeNode start;
TreeNode end;
public Result(TreeNode start, TreeNode end) {
this.start = start;
this.end = end;
}
}
private void solve(TreeNode root) {
Result res = flatten(root);
TreeNode curr = res.start;
while (curr != null) {
System.out.print(curr.x + " ");
curr = curr.right;
}
System.out.println();
}
private Result flatten(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) {
return new Result(root, root);
}
if (root.left == null) {
Result right = flatten(root.right);
right.end.right = root;
root.right = null;
return new Result(right.start, root);
} else if (root.right == null) {
Result left = flatten(root.left);
left.end.right = root;
root.right = null;
return new Result(left.start, root);
} else {
Result left = flatten(root.left);
Result right = flatten(root.right);
left.end.right = right.start;
right.end.right = root;
root.right = null;
return new Result(left.start, root);
}
}
}
// Reversed BFS traversal
using System;
using System.Collections.Generic;
public class Test
{
static Stack<Node> internalStack = new Stack<Node>();
class Node
{
public Node(int value, Node left, Node right)
{
Left = left;
Right = right;
Value = value;
}
public readonly Node Left;
public readonly Node Right;
public readonly int Value;
}
public static void Main()
{
// your code goes here
var root = new Node(1, new Node(2, new Node(4, null, null), new Node(5, null, null)),
new Node(3, new Node(6, null, null), new Node(7, null, null)));
internalStack.Push(root);
Visit(root);
while(internalStack.Count > 0)
{
var item = internalStack.Pop();
Console.Write(item.Value);
}
}
private static void Visit(Node root)
{
if(root == null) return;
if(root.Right != null)
{
internalStack.Push(root.Right);
}
if(root.Left != null)
{
internalStack.Push(root.Left);
}
Visit(root.Right);
Visit(root.Left);
}
}
I push the children nodes from right to left, so each level is printed from left to right:
public void printTree(Node root){
Queue<Node> nodes = new Queue<>();
if(root != null)
nodes.add(root);
Stack<Integer> result = new Stack<>();
while(!nodes.isEmpty()){
Node node = nodes.pop();
result.add(node.val);
if(node.right != null)
nodes.add(node.right);
if(node.left != null)
nodes.add(node.left);
}
while(!result.isEmpty())
System.out.print(result.pop() + “ “);
}
public static void downUp(BNode node) {
Queue<BNode> q = new LinkedList<BNode>();
Stack<Integer> s = new Stack<Integer>();
q.add(node);
while (!q.isEmpty()) {
BNode node1 = q.remove();
s.push(node1.val);
if (node1.right != null) {
q.add(node1.right);
}
if (node1.left != null) {
q.add(node1.left);
}
}
while (!s.isEmpty()) {
System.out.println(s.pop());
}
}
List<Integer> levelOrderTraversal(Node root)
{
if(root == null)
{
throw new IllegalArgumentException("what the hell");
}
Queue<Node> queue = new ArrayDeque<>();
List<Integer> levelOrder = new ArrayList<>();
queue.add(root);
while(queue.isEmpty() == false)
{
Node current = queue.remove();
levelOrder.add(0, current.data);
if(current.left != null)
{
queue.add(current.left);
}
if(current.right != null)
{
queue.add(current.right);
}
}
return levelOrder;
}
Do a level traversal (in order) you will end up with a List of Lists, each one representing one level, now start from last element of array and keep iterating backwards (this will print all leaf nodes first until you reach root which is the desired answer). Time: O (n) Space O (n)
- Anonymous November 09, 2016