Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
This question is the same which require newline feed in the previously asked question instead of newline feed you can replace it with carriage return.
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static class Node
{
char value;
Node left;
Node right;
public Node(char in)
{
this.value = in;
this.left = null;
this.right = null;
}
}
static class Tree
{
Node root;
public Tree(Node r)
{
this.root = r;
}
public void treeBFS()
{
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
int count = 0;
while(!queue.isEmpty())
{
if(count == 0)
count = queue.size();
Node c = queue.poll();
count = count-1;
if(c != null)
{
if(count == 0)
{
System.out.print(" "+c.value);
System.out.println(" ");
}
else
{
System.out.print(" "+c.value);
}
if(c.left != null);
{
queue.add(c.left);
}
if(c.right != null)
{
queue.add(c.right);
}
}
}
}
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Node A = new Node('A');
Node B = new Node('B');
Node C = new Node('C');
Node D = new Node('D');
Node E = new Node('E');
Node F = new Node('F');
Node G = new Node('G');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
Tree root = new Tree(A);
root.treeBFS();
}
}
Actually you could do that using a Queue and anther Queue just to maintain in the right order when printing.
public class Node<T>
{
public Node<T> Left {get; set;}
public Node<T> Right {get;set;}
public T Data {get; set;}
}
private class NodeLevel<T>
{
public Node<T> Node {get; set;}
public int Level {get; set;}
}
static public string GetBinaryTreeRows<T>(Node<T> root)
{
if(root == null) return null;
Queue<NodeLevel<T>> Q = new Queue<NodeLevel<T>>();
Queue<NodeLevel<T>> S = new Queue<NodeLevel<T>>();
Q.Enqueue(new NodeLevel<T>(){ Node=root, Level=0});
while(Q.Count > 0)
{
NodeLevel<T> np = Q.Dequeue();
Node<T> n = np.Node;
S.Enqueue(np);
if(n.Left != null)
{
Q.Enqueue(new NodeLevel<T>(){
Node = n.Left,
Level = np.Level + 1});
}
if(n.Right != null)
{
Q.Enqueue(new NodeLevel<T>(){
Node = n.Right,
Level = np.Level + 1});
}
}
StringBuilder sb = new StringBuilder();
int lastLevel = 0;
while(S.Count > 0)
{
NodeLevel<T> np = S.Dequeue();
if(np.Level != lastLevel)
{
lastLevel= np.Level;
sb.Append("\n");
}
sb.Append(np.Node.Data.ToString());
sb.Append(" ");
}
return sb.ToString();
}
I've tested using this code. Does not seem clear the tree but it looks like this:
(d)
/ \
(b) (g)
/ \ / \
(a) (c) (e) (h)
\
(f)
void Main()
{
// Tree
// a - h
Node<string> root = new Node<string>(){
Data = "d",
Left = new Node<string>(){
Data = "b",
Left = new Node <string> ()
{
Data = "a"
},
Right = new Node<string>()
{
Data = "c"
}
},
Right = new Node<string>()
{
Data = "g",
Left = new Node<string>()
{
Data = "e",
Right = new Node<string>()
{
Data = "f"
}
},
Right = new Node<string>()
{
Data = "h"
}
}
};
string expected = "d \nb g \na c e h \nf ";
string output = GetBinaryTreeRows(root);
Console.WriteLine(output);
if(output != expected)
{
throw new Exception("Test Failed");
}
}
ID (Iterative Deepening solution). Please recall that ID has same asymptotic time complexity as either BFS or DFS.
public static void printLevels(Node root) {
int depth=0;
while(printDepth(root, 0, depth) > 0){
depth++;
System.out.println();
}
}
public static int printDepth(Node curNode, int curDepth, int targetDepth) {
if (curDepth==targetDepth){
System.out.print(curNode.val());
return 1;
}
int sum=0;
if (curNode.left() != null) {
sum += printDepth(curNode.left(), curDepth+1,targetDepth);
}
if (curNode.right() != null) {
sum += printDepth(curNode.right(), curDepth+1,targetDepth);
}
return sum;
}
O(n) runtime complexity and O(log n) max memory (it seems like someone asks this question at least once a week...):
class Node{
Node left, right;
char c;
}
public static void print(Node node){
if(node == null){
return;
}
LinkedList<Node> list = new LinkedList<Node>();
LinkedList<Node> alt = new LinkedList<Node>();
LinkedList<Node> temp;
list.add(node);
StringBuilder b = new StringBuilder();
while(!list.isEmpty()){
while(!list.isEmpty()){
node = list.removeFirst());
if(node.left != null){
alt.add(node.left);
}
if(node.right != null){
alt.add(node.right);
}
b.append(node.c);
}
System.out.println(b.toString());
b.setLength(0);
temp = list;
list = alt;
alt = temp;
}
}
Take a array of n/2 size that's the maximum length the output can be.Initialize it with INT_MAX or INT_MIN.
Take an index i which always point to the first element in this array
Do level order traversal and put the elements in the array in the order we traverse. By now the index points to the last element of the current row. After completing each row intialize the index again to the starting index of the array and repeat till all rows are exhausted.
import java.util.LinkedList;
import java.util.Queue;
class BinaryTreeRows {
public static void main (String [] args) {
Node root = new Node(8);
root.left = new Node(1);
root.left.left = new Node(3);
root.left.left.left = new Node(4);
root.left.left.left.right = new Node(3);
root.left.right = new Node(6);
root.left.right.right = new Node(2);
root.right = new Node(9);
root.right.left = new Node(-1);
root.right.right = new Node(6);
printTree(root);
}
public static void printTree(Node node) {
Queue<Node> queue = new LinkedList<Node>();
queue.offer(node);
boolean newLevel = true;
int levelCount = 0, currentCount = 0;
while (queue.size() != 0) {
if (newLevel == true) {
System.out.println("\n");
newLevel = false;
levelCount = queue.size();
currentCount = 0;
}
Node element = queue.poll();
System.out.print(element.value + "\t");
if (element.left != null) {
queue.offer(element.left);
}
if (element.right != null) {
queue.offer(element.right);
}
currentCount++;
if (currentCount == levelCount) {
newLevel = true;
}
}
}
}
class Node {
Node left;
Node right;
int value;
Node (int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
import java.io.*;
import java.util.*;
class Node
{
int data;
public Node left;
public Node right;
public Node(int d)
{
this.data=d;
this.left=null;
this.right=null;
}
}
class printtree
{
public static HashMap<Integer,List<Node>> gs;
public static void main(String[] args)
{
Node root = new Node(1);
root.left = new Node(2);
root.right= new Node(3);
root.left.left=new Node(4);
root.left.right=new Node(5);
root.right.left=new Node(6);
root.right.right=new Node(7);
print(root);
}
public static void print(Node root)
{
gs=new HashMap<Integer,List<Node>>();
func(root,1);
int i=1;
while(gs.containsKey(i))
{
for(Node n : gs.get(i))
{
System.out.print(n.data+",");
}
System.out.println("");
i++;
}
}
public static void func(Node node, int i)
{
if(!gs.containsKey(i))
gs.put(i,new ArrayList<Node>());
gs.get(i).add(node);
if(node.left!=null)
func(node.left,i+1);
if(node.right!=null)
func(node.right,i+1);
}
}
Here is an efficient java solution:
import java.io.*;
import java.util.*;
class Node
{
int data;
public Node left;
public Node right;
public Node(int d)
{
this.data=d;
this.left=null;
this.right=null;
}
}
class printtree
{
public static HashMap<Integer,List<Node>> gs;
public static void main(String[] args)
{
Node root = new Node(1);
root.left = new Node(2);
root.right= new Node(3);
root.left.left=new Node(4);
root.left.right=new Node(5);
root.right.left=new Node(6);
root.right.right=new Node(7);
print(root);
}
public static void print(Node root)
{
gs=new HashMap<Integer,List<Node>>();
func(root,1);
int i=1;
while(gs.containsKey(i))
{
for(Node n : gs.get(i))
{
System.out.print(n.data+",");
}
System.out.println("");
i++;
}
}
public static void func(Node node, int i)
{
if(!gs.containsKey(i))
gs.put(i,new ArrayList<Node>());
gs.get(i).add(node);
if(node.left!=null)
func(node.left,i+1);
if(node.right!=null)
func(node.right,i+1);
}
}
import java.io.*;
import java.util.*;
class Node
{
int data;
public Node left;
public Node right;
public Node(int d)
{
this.data=d;
this.left=null;
this.right=null;
}
}
class printtree
{
public static HashMap<Integer,List<Node>> gs;
public static void main(String[] args)
{
Node root = new Node(1);
root.left = new Node(2);
root.right= new Node(3);
root.left.left=new Node(4);
root.left.right=new Node(5);
root.right.left=new Node(6);
root.right.right=new Node(7);
print(root);
}
public static void print(Node root)
{
gs=new HashMap<Integer,List<Node>>();
func(root,1);
int i=1;
while(gs.containsKey(i))
{
for(Node n : gs.get(i))
{
System.out.print(n.data+",");
}
System.out.println("");
i++;
}
}
public static void func(Node node, int i)
{
if(!gs.containsKey(i))
gs.put(i,new ArrayList<Node>());
gs.get(i).add(node);
if(node.left!=null)
func(node.left,i+1);
if(node.right!=null)
func(node.right,i+1);
}
}
import java.io.*;
import java.util.*;
class Node
{
int data;
public Node left;
public Node right;
public Node(int d)
{
this.data=d;
this.left=null;
this.right=null;
}
}
class printtree
{
public static HashMap<Integer,List<Node>> gs;
public static void main(String[] args)
{
Node root = new Node(1);
root.left = new Node(2);
root.right= new Node(3);
root.left.left=new Node(4);
root.left.right=new Node(5);
root.right.left=new Node(6);
root.right.right=new Node(7);
print(root);
}
public static void print(Node root)
{
gs=new HashMap<Integer,List<Node>>();
func(root,1);
int i=1;
while(gs.containsKey(i))
{
for(Node n : gs.get(i))
{
System.out.print(n.data+",");
}
System.out.println("");
i++;
}
}
public static void func(Node node, int i)
{
if(!gs.containsKey(i))
gs.put(i,new ArrayList<Node>());
gs.get(i).add(node);
if(node.left!=null)
func(node.left,i+1);
if(node.right!=null)
func(node.right,i+1);
}
}
void printTree(){
Queue q= new LinkedList();
int curLevel=0;
int nextLevel=0;
q.add(root);
curLevel++;
while(!q.isEmpty()){
Node x=(Node) q.remove();
curLevel--;
System.out.print(x.value+" ");
if(x.lChild!=null)
{
q.add(x.lChild);
nextLevel++;
}
if(x.rChild!=null)
{
q.add(x.rChild);
nextLevel++;
}
if(curLevel==0)
{
curLevel=nextLevel;
nextLevel=0;
System.out.print("\n");;
}
}
}
Initialize 2 parameters currentLevel and nextLevel. when currentLevel=0 then next level becomes currentLevel.
void printT(){
Queue q= new LinkedList();
int curLevel=0;
int nextLevel=0;
q.add(root);
curLevel++;
while(!q.isEmpty()){
Node x=(Node) q.remove();
curLevel--;
System.out.print(x.value+" ");
if(x.lChild!=null)
{
q.add(x.lChild);
nextLevel++;
}
if(x.rChild!=null)
{
q.add(x.rChild);
nextLevel++;
}
if(curLevel==0)
{
curLevel=nextLevel;
nextLevel=0;
System.out.print("\n");;
}
}
}
We can use a breadth-first traversal, taking advantage of the fact that it's a binary tree (number of nodes doubles at each level as we move down the tree)
void printBinaryTree(Node root) {
Queue<Node> q = new LinkedList<>();
q.add(root);
int visitedNodeCount = 0;
int printNewLineAt = 1;
while (!q.isEmpty()) {
Node n = q.poll();
if (n.left != null) {
q.add(n.left);
}
if (n.right != null) {
q.add(n.right);
}
print(node.data);
visitedNodeCount++;
if (visitedNodeCount == printNewLineAt) {
printNewLineAt *= 2;
print('\n');
}
}
}
C++ solution with BFS.
#include <list>
#include <iostream>
using namespace std;
struct node {
node* left;
node* right;
int value;
node(int v):value(v),left(0), right(0){}
};
void print_tree(node * root)
{
list<node *>queue;
int cur_children = 0;
int next_children = 0;
if (!root)
return;
queue.push_back(root);
cur_children++;
while(queue.size())
{
node* cur = queue.front();
queue.pop_front();
if (cur->left)
{
queue.push_back(cur->left);
next_children++;
}
if (cur->right)
{
queue.push_back(cur->right);
next_children++;
}
cout<<cur->value<<" ";
if (--cur_children == 0)
{
cout<<endl;
cur_children = next_children;
next_children = 0;
}
}
}
Use a queue to perform BFS. Enqueue 'null' at the end of each depth. Print the node values as they come from the queue. When you see 'null' then (i) print carriage return character (ii) enqueue null again. Do until queue size is 1 and contains only 'null'.
A sample code is below:
- autoboli January 09, 2015