Facebook Interview Question
SDE1sCountry: United States
Question specifically says use stack and recursion. Cannot use any other data structure like queue, list or vector to store the result and print it. Idea of question is to exploit recursion as a way of storing the result string.
import java.util.Stack;
public class PrintBTReverseLevel {
static class Node {
int value;
Node left;
Node right;
Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
public void addLeftNode(int value) {
Node n = new Node(value);
this.left = n;
}
public void addRightNode(int value) {
Node n = new Node(value);
this.right = n;
}
}
static int LEFTRIGHT = 0;
static int RIGHTLEFT = 1;
//called with root node and RIGHTLEFT as direction
private static void printReverseLevelOrder(Stack<Node> stack, int direction) {
if(stack.isEmpty())
return;
//Go to next level
Stack<Node> nextLevel = new Stack<Node>();
String currentLevel = "";
while(!stack.isEmpty()) {
Node p = stack.pop();
if(direction==RIGHTLEFT) {
if(p.right!=null)
nextLevel.push(p.right);
if(p.left!=null)
nextLevel.push(p.left);
}else {
if(p.left!=null)
nextLevel.push(p.left);
if(p.right!=null)
nextLevel.push(p.right);
}
if(direction==LEFTRIGHT) {
//Add in currentLevel String as popped
currentLevel += p.value+",";
}else {
//Add in currentLevel String in reverse order
currentLevel = p.value + "," + currentLevel;
}
}
printReverseLevelOrder(nextLevel, (direction==RIGHTLEFT)?LEFTRIGHT:RIGHTLEFT);
currentLevel = currentLevel.substring(0, currentLevel.length()-1);
currentLevel = "[" + currentLevel + "],";
System.out.println(currentLevel);
//Print current stack
}
public static void main(String args[]) {
Node root = new Node(1);
root.addLeftNode(2);
root.addRightNode(3);
root.left.addLeftNode(4);
root.left.addRightNode(5);
root.right.addLeftNode(6);
root.right.addRightNode(7);
root.left.left.addLeftNode(8);
root.left.right.addLeftNode(9);
root.left.right.addRightNode(10);
Stack<Node> stack = new Stack<Node>();
stack.push(root);
System.out.println("[");
printReverseLevelOrder(stack, RIGHTLEFT);
System.out.println("]");
}
}
Printing from the array -
public static void main(String args[]){
Integer[] nodes = {3, 9, 20, null, null, 15, 7};
printFromLeaf(nodes, 1);
System.out.println(nodes[0]);
}
public static void printFromLeaf(Integer[] nodes, int index){
int n = nodes.length-1;
if(index > n)
return;
int left = index*2;
int right = index*2 + 1;
if(left-1 <= n && nodes[left-1] != null)
printFromLeaf(nodes, left);
if(right-1 <= n && nodes[right-1] != null)
printFromLeaf(nodes, right);
if(left-1 <= n && right-1 <= n && nodes[left-1] != null && nodes[right-1] != null)
System.out.println(nodes[left-1] + ", " + nodes[right-1]);
}
import sys
items = sys.stdin.readline().strip().split(' ')
tree_definition = []
for i in items:
if i != 'None':
tree_definition.append(int(i))
else:
tree_definition.append(None)
levels = {}
def add(tree, idx, level):
if idx <= len(tree) and tree[idx] != None:
# Add to my level
if level in levels:
levels[level].append(tree[idx])
else:
levels[level] = [ tree[idx] ]
# Add left subtree to next level
add(tree, idx*2+1, level+1)
# Add right subtree to next level
add(tree, idx*2+2, level+1)
add(tree_definition, 0, 0)
n = len(levels.keys())
for i in range(n):
level = n-1-i
print "{}".format(" ".join(map(str, levels[level])))
Use a Queue to do level order traversal. When putting nodes in Q, also put the levels.
Every time we pop from the Queue, push to the stack along with the level. Next, push the right child in the Queue (node.right, level+1) and THEN push the left child in the Queue.
In the end, stack has the data we need.
class Node:
def __init__(self, val, left, right):
self.left = left
self.right = right
self.val = val
def get_left(self):
return self.left
def get_right(self):
return self.right
def get_val(self):
return self.val
root = Node(5,
Node(3,
Node(2, Node(11, None, None), Node(10, None, None)),
Node(22, None, None)
),
Node(2,
Node(11,
Node(15, Node(16, None, None), Node(17, None, None)),
Node(18, Node(19, None, None), Node(20, None, None))
),
Node(10, None, None)
)
)
def append_child(node):
children = []
if node.get_left():
children.append(node.get_left())
if node.get_right():
children.append(node.get_right())
return children
def get_values(arr):
return list(map(lambda x: x.get_val(), arr));
def get_levels_in_reverse(stack):
tmp = []
item = stack.pop();
while item:
tmp.append(item)
if len(stack) > 0:
item = stack.pop()
else:
item = None
for node in tmp:
stack.extend(append_child(node));
if len(stack) > 0:
return [get_values(tmp)] + get_levels_in_reverse(stack)
return [get_values(tmp)]
print(get_levels_in_reverse([root]))
JavaScript solution
function helper(node, level, solution){
if (!node){
return;
}
if (level > solution.length - 1){
solution.push([]);
}
solution[level].push(node.value);
helper(node.left, level + 1, solution);
helper(node.right, level + 1, solution);
}
function levelOrderBottom(root){
const solution = [];
helper(root, 0, solution);
return solution.reverse();
}
const root = {
value: 3,
left: {
value: 9,
left: null,
right: null
},
right: {
value: 20,
left: {
value: 15,
left: null,
right: null
},
right: {
value: 7,
left: null,
right: null
},
},
};
console.log(levelOrderBottom(root));
In python this should do it:
def levelOrderBottom(root):
l = []
previous_level = 0
queue = [(root,1)]
while queue:
node, height = queue.pop(0)
if height != previous_level:
l.append([])
previous_level = height
l[-1].append(node.data)
if node.left is not None:
queue.append((node.left, height+1))
if node.right is not None:
queue.append((node.right, height+1))
return l[::-1]
Assuming a data structure like this:
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
root = Node(3)
root.left = Node(9)
root.right = Node(20, Node(15), Node(7))
printReverseTree();
function createNode(value){
var node = {val: value, left: null, right: null};
return node;
}
function createTree() {
var node20 = createNode(20);
node20.left = createNode(15);
node20.right = createNode(7);
var tree = createNode(3);
tree.left = createNode(9);
tree.right = node20;
return tree
}
function printReverseTree(){
var tree = createTree();
var result = print(tree, 0, []);
result = result.reverse();
result.forEach(item => {
console.log(item);
});
}
function print(node, depth, result){
if(node.left){
print(node.left, depth + 1, result);
}
if(node.right){
print(node.right, depth + 1, result);
}
if(!result[depth])
result[depth] = [];
result[depth].push(node.val);
return result;
}
void bottom_up_level_traversal_aux(tree t, std::vector<std::vector<int>>& res, int level) {
if (t == nullptr) {
return;
}
bottom_up_level_traversal_aux(t->left, res, level + 1);
bottom_up_level_traversal_aux(t->right, res, level + 1);
if (res.size() < level + 1) {
res.resize(level + 1);
}
res[level].push_back(t->value);
}
std::vector<std::vector<int>> bottom_up_level_traversal(tree t) {
std::vector<std::vector<int>> output;
bottom_up_level_traversal_aux(t, output, 0);
std::reverse(output.begin(), output.end());
return output;
}
vector<vector<int>> levelOrderBottom(TreeNode *root)
{
if(root == NULL)
return vector<vector<int>> ();
vector<vector<int>> res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
int size = q.size();
vector<int> v;
for(int i=0; i<size; i++)
{
TreeNode *cur = q.front();
q.pop();
v.push_back(cur->val);
if(cur->left != NULL)
q.push(cur->left);
if(cur->right != NULL)
q.push(cur->right);
}
res.push_back(v);
}
reverse(res.begin(), res.end());
return res;
}
vector<vector<int>> levelOrderBottom(TreeNode *root)
{
if(root == NULL)
return vector<vector<int>> ();
vector<vector<int>> res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
int size = q.size();
vector<int> v;
for(int i=0; i<size; i++)
{
TreeNode *cur = q.front();
q.pop();
v.push_back(cur->val);
if(cur->left != NULL)
q.push(cur->left);
if(cur->right != NULL)
q.push(cur->right);
}
res.push_back(v);
}
reverse(res.begin(), res.end());
return res;
}
vector<vector<int>> levelOrderBottom(TreeNode *root)
{
if(root == NULL)
return vector<vector<int>> ();
vector<vector<int>> res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
int size = q.size();
vector<int> v;
for(int i=0; i<size; i++)
{
TreeNode *cur = q.front();
q.pop();
v.push_back(cur->val);
if(cur->left != NULL)
q.push(cur->left);
if(cur->right != NULL)
q.push(cur->right);
}
res.push_back(v);
}
reverse(res.begin(), res.end());
return res;
}
Pretty straight forward. The only thing to remember here is that when using "stack" we should push the "right" node before we push the "left" node (stack is FILO)
- PenChief October 02, 2017