CareerCup

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)

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)
}

Write level order traversal algo, just store the element in array and print the array in reverse order.

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();
	}

void traverse(root){
	Queue q = new Queue();
	q.addLast(root)
	while(!q.isEmpty()){
		root r = q.removeFirst();
		res += r.val;
		q.addLast(r.right);
		q.addLast(r.left);
	}
	sout(res.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);
}
}

can't we just use a stack and pre-order traversal here, i.e. stack.push(current), stack.push(left), stack.push(right)

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() + “ “);


}

can't you just do this with simple recursion?
Post Order Traversal

void postOrder(TreeNode* root){
	if (root== NULL) return;
	postOrder(root->left);
	postOrder(root->right);
	cout << root->val << " ";

}

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;
}

BFS going right to left starting at root and print reverse of path time and space O(n)