Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
#include <iostream>
#include <vector>
using namespace std;
struct Node {
char name;
Node* left;
Node* right;
Node* next;
};
void fillNext(Node* node, vector<Node*>& depthNodes, int depth) {
Node* prev;
if (node == NULL) return;
if (depthNodes.size() > depth) {
prev = depthNodes[depth];
if (prev) {
prev->next = node;
cout << prev->name << " - " << node->name << "\n";
}
depthNodes[depth] = node;
} else {
depthNodes.push_back(node);
}
fillNext(node->left, depthNodes, depth + 1);
fillNext(node->right, depthNodes, depth + 1);
}
int main(int argc, char* argv[]) {
Node A, B, C, D, F, G, H, I;
vector<Node*> depthNodes;
A.name = 'A';
A.left = &B;
A.right = &C;
A.next = NULL;
B.name = 'B';
B.left = &D;
B.right = NULL;
B.next = NULL;
C.name = 'C';
C.left = &F;
C.right = &G;
C.next = NULL;
D.name = 'D';
D.left = &H;
D.right = &I;
D.next = NULL;
F.name = 'F';
F.left = NULL;
F.right = NULL;
F.next = NULL;
G.name = 'G';
G.left = NULL;
G.right = NULL;
G.next = NULL;
H.name = 'H';
H.left = NULL;
H.right = NULL;
H.next = NULL;
I.name = 'I';
I.left = NULL;
I.right = NULL;
I.next = NULL;
depthNodes.clear();
fillNext(&A, depthNodes, 0);
depthNodes.clear();
return 0;
}
public class GetRightNode {
public static class Node {
char c;
Node left;
Node right;
Node next;
}
public static void main(String[] args) {
Node a = new Node();
a.c = 'A';
Node b = new Node();
b.c = 'B';
Node c = new Node();
c.c = 'C';
Node d = new Node();
d.c = 'D';
Node f = new Node();
f.c = 'F';
Node g = new Node();
g.c = 'G';
Node h = new Node();
h.c = 'H';
Node i = new Node();
i.c = 'I';
a.left = b;
a.right = c;
b.left = d;
c.left = f;
c.right =g;
d.left = h;
d.right = i;
setNextNode(a);
System.out.println(a.c + "->" + (a.next != null ? a.next.c : ""));
System.out.println(b.c + "->" + (b.next != null ? b.next.c : ""));
System.out.println(c.c + "->" + (c.next != null ? c.next.c : ""));
System.out.println(d.c + "->" + (d.next != null ? d.next.c : ""));
System.out.println(f.c + "->" + (f.next != null ? f.next.c : ""));
System.out.println(g.c + "->" + (g.next != null ? g.next.c : ""));
System.out.println(h.c + "->" + (h.next != null ? h.next.c : ""));
System.out.println(i.c + "->" + (i.next != null ? i.next.c : ""));
}
public static void setNextNode(Node root) {
if(root == null || (root.left == null && root.right == null)) return;
LinkedList<Node>q = new LinkedList<Node>();
q.add(root);
q.add(null);
Node prev = null;
while(!q.isEmpty()) {
Node n = q.remove();
if(n != null) {
if(prev != null) prev.next=n;
prev = n;
if(n.left != null) q.add(n.left);
if(n.right != null) q.add(n.right);
} else {
prev = null;
if(!q.isEmpty()) q.add(null);
}
}
}
}
Following solution is pretty good
oid setNext(Node root) {
List<List<Node>> masterList = new ArrayList<>();
setN(root, 0, masterList);
for(int i=0; i<masterList.size(); i++) {
List<Node> temp = masterList.get(i);
for(int j=0; j<temp.size(); j++) {
if(temp.get(j+1) != null) {
Node tempNode = temp.get(j);
tempNode.next = temp.get(j+1);
} else {
Node tempNode = temp.get(j);
tempNode.next = null;
}
}
}
}
void setN(Node node, int level, List<List<Node>> mList) {
if(node == null) return;
if(mList.get(level) == null) {
mList.add(new ArrayList<Node>());
}
List<Node> nodesAtLevel = mList.get(level);
nodesAtLevel.add(node);
setN(node.left, level + 1, mList);
setN(node.right, level + 1, mList);
}
Hi,
if i define parent and next child as another pointer in the Node structure which basically has Left and Child initially...then while inserting a node itself i can populate the next pointer.
My only concern is i end up modifying the structure of Node ....how good that approach be ? also Question ask to define next pointer in the Node ..which is again an alteration of Node structure.
Use BFS adding nodes to a queue keeping a parent pointer in a WrapperNode entry
class WrapperNode {
Node parent;
Node node;
public WrapperNode (Node node){
this(node,null);
}
public WrapperNode (Node node, Node parent){
this.parent = parent;
this.node = node;
}
}
public void assignNextNodes( Node root){
Queue<WrapperNode> queue = new LinkedBlockingQueue<WrapperNode >();
queue.enqueue(new WrapperNode(root));
while(!queue.isEmpty()){
WrapperNode current = queue.dequeue();
WrapperNode next = queue.peekHead();
if(next == null|| current.parent != next.parent){
current.node.next = null;
}else {
current.node.next = next.node;
}
queue.enqueue(new WrapperNode(current.node.left,node));
queue.enqueue(new WrapperNode(current.node.right,node));
}
}
class WrapperNode {
Node parent;
Node node;
public WrapperNode (Node node){
this(node,null);
}
public WrapperNode (Node node, Node parent){
this.parent = parent;
this.node = node;
}
}
public void assignNextNodes( Node root){
Queue<WrapperNode> queue = new LinkedBlockingQueue<WrapperNode >();
queue.enqueue(new WrapperNode(root));
while(!queue.isEmpty()){
WrapperNode current = queue.dequeue();
WrapperNode next = queue.peekHead();
if(next == null|| current.parent != next.parent){
current.node.next = null;
}else {
current.node.next = next.node;
}
queue.enqueue(new WrapperNode(current.node.left,node));
queue.enqueue(new WrapperNode(current.node.right,node));
}
}
{
class WrapperNode {
Node parent;
Node node;
public WrapperNode (Node node){
this(node,null);
}
public WrapperNode (Node node, Node parent){
this.parent = parent;
this.node = node;
}
}
public void assignNextNodes( Node root){
Queue<WrapperNode> queue = new LinkedBlockingQueue<WrapperNode >();
queue.enqueue(new WrapperNode(root));
while(!queue.isEmpty()){
WrapperNode current = queue.dequeue();
WrapperNode next = queue.peekHead();
if(next == null|| current.parent != next.parent){
current.node.next = null;
}else {
current.node.next = next.node;
}
queue.enqueue(new WrapperNode(current.node.left,node));
queue.enqueue(new WrapperNode(current.node.right,node));
}
}
}
public static void PopulateNext(Node root)
{
if(root == null) return;
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
q.Enqueue(null)
Node cur = null;
while(q.Count > 0)
{
Node t = q.Dequeue();
if(cur == null)
{
cur = t;
}
else
{
cur.Next = t;
cur = t;
}
if(t != null)
{
if(t.Left != null)
{
q.Enqueue(t.Left);
}
if(t.Rigth != null)
{
q.Enqueue(t.Right);
}
}
else if(q.Count > 0)
{
q.Enqueue(null);
}
}
}
Java solution --> The main idea is that if we find the next node of the current node, then the next of the last children of current node should be the first next children found. the while loop for next takes care of this. Please comment if you find any issues -
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.LinkedList;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
Node node = new Node(20);
node.left = new Node(9);
node.right = new Node(49);
node.left.right = new Node(12);
node.left.left = new Node(5);
//node.left.right.right = new Node(15);
node.right.right = new Node(52);
node.right.left = new Node(23);
// node.right.right.left = new Node(50);
print(makeLink(node));
}
public static void print(Node node){
if(node == null) return;
System.out.println("node.data " + node.data + " node.next " + node.next + "->");
print(node.left);
print(node.right);
}
public static Node makeLink(Node root){
Queue<Node> q = new LinkedList<Node>();
q.add(root);
while(!q.isEmpty()){
Node node = q.remove();
System.out.println("node data " + node.data);
Node tmp = node.next;
if(tmp != null){
if(node.right == null && node.left != null){
while(tmp != null){
if(tmp.left!=null){
node.left.next = tmp.left;
break;
}else if(tmp.right != null){
node.left.next = tmp.right;
break;
}else {
tmp = tmp.next;
}
}
} else if(node.right != null){
while(tmp != null){
if(tmp.left!=null){
node.right.next = tmp.left;
break;
}else if(tmp.right != null){
node.right.next = tmp.right;
break;
}else {
tmp = tmp.next;
}
}
}
}
if(node.left != null && node.right != null){
node.left.next = node.right;
q.add(node.left);
q.add(node.right);
} else if(node.left != null){
q.add(node.left);
} else if(node.right != null){
q.add(node.right);
}
}
return root;
}
}
class Node{
int data;
Node left;
Node right;
Node next;
public Node(int data){
this.data = data;
}
}
Pass an array of nodes in the solve function. For each nodes, push the left and right children in an array. When done, assign each node in the array to the next one.
Call solve on those children.
At the beginning, call solve on an array of size 1 with the root only.
function solve(roots) {
var children = [];
for(var i=0;i<roots.length;i++) {
var root = roots[i];
if(root.left)
children.push(root.left);
if(root.right)
children.push(root.right);
}
for(var i=0;i<children.length-1;i++) {
children[i].next = children[i+1];
}
solve(children);
}
Tackling this with a modified BFS using marker points. Expecting this to work on any type of tree or graph and not just binary tree.
In your BFS algorithm where pop() and insert back all the elements in the same queue.
modify this to use a pointer in an array so that you don't really remove it but instead just peeks and behaves logically as a queue.
before inserting the all children of the node you just peeked put the marker of #ofChildren.
Also lets start not with a root but something above the root. This makes it very simple. Don't worry if it sounded tricky, see below for simple explanation:
For the given tree:
start
|
A
/ \
B -> C
/ / \
D -> F-> G
/ \
H -> I
Put each element in the queue using markers as below:
1 A 2 BC 1 D 2 FG 2 HI
Read this as : There is 1 node i.e. A, there are 2 children of A: B and C, B has 1 child D,C has 2 child F,G. and so on. You don't need this information anyways, but just incase if you wondering how did I modify the BFS here with some markers but still a BFS if read without markers.
Now use this BFS with markers to build up the neighbors.
//base for root node - no marker and only 1 root node
#ofMarkersToEvaluate = 0;
#ofNodes = 1;
prev = null;
while (!queue.isEmpty()) {
#ofNodes = queue.take()
if (prev == null) {
prev = queue.take();
}
while (#ofNodes > 1) {
nextNode = queue.take();
prev.next = nextNode;
prev = nextNode;
#ofNodes--;
}
// on the same level, preserve the previous node
if (ofMarkersToEvaluate > 0 )
#ofMarkersToEvaluate --;
continue;
}
//reset prev for a new level
prev = null;
}
void get_next(Node *root)
{
queue<Node*> q;
q.push(root);q.push(nullptr);
Node *pre = nullptr;
while (!q.empty()) {
Node *node = q.front(); q.pop();
if(pre == nullptr) pre = node;
else pre->next = node;
if(node && node -> left) q.push(node->left);
if(node && node -> right) q.push(node->right);
}
}
Can use recursion here efficiently. It works in both C# and Java as the left, right and next Node elements are references to the objects allocated for the tree. This is cheap in use of space. Each call stack has a reference to the original root node defined in your main.
public class Node {
String Name;
Node next;
Node right;
Node left;
public Node(String name) {
Name = name;
}
}
void PopulateNext(Node node){
if (node != null) {
node.next = node.right;
PopulateNext(node.left);
PopulateNext(node.right);
}
}
void PrintNodes(Node node) {
if (node != null)
{
System.out.println(
node.Name + ".next=" +
(node.next != null ? node.next.Name : "null"));
PrintNodes(node.right);
PrintNodes(node.left);
}
}
We can do a reversed BFS traversal. For each node, queue its right before its left. Remember the last dequeued node, set it as 'next' of the current dequeued node.
This will make all nodes at the same level points to the right one, except the right-most one will point to the first one at the upper level. We rectify this by traversing thru all the right-most nodes from root, and clear their 'next'.
My idea is do traverse the tree as you normally would. If we find the node that we are at the same node as the node calling next, then any node to the right of me is a possibility as my next, since we are traversing from left to right (if they are at the same depth). If we ever have the depth as the same as the desired depth, then set the result (if it hasn't been set yet). Any subtrees below our "next" and to the right wont be processed since we return out if we have result.
public BTNode Next(BTNode root)
{
// if root is our desired next node, we know it's null
if (root.Value == this.Value)
{
return null;
}
// our desired depth
int desired = -1;
// our final result
BTNode next = null;
// call the recursive call
Next(root, 0, ref desired, ref next);
// the result
return next;
}
private void Next(BTNode curr, int depth, ref int desiredDepth, ref BTNode result)
{
// if we have a null current, then don't process anything
if (curr == null)
{
return;
}
// if we already have a result, just return out
if (result != null)
{
return;
}
// if our current node is same node, then we have found the node, so set our depth
if (curr.Value.Equals(this.Value))
{
desiredDepth = depth;
return;
}
// we have previously found the depth we want
// if we haven't set our result yet, then set it, and return
if (desiredDepth == depth && result == null)
{
result = curr;
return;
}
// recurse from left to right, incrementing depth
Next(curr.Left, depth + 1, ref desiredDepth, ref result);
Next(curr.Right, depth + 1, ref desiredDepth, ref result);
}
using System;
using System.Collections.Generic;
// To execute C#, please define "static void Main" on a class
// named Solution.
public class Node<T>
{
public T Data;
public Node(T data)
{
Data=data;
}
}
public class BinaryTree<T> : Node<T>
{
public BinaryTree<T> Left;
public BinaryTree<T> Right;
public int Depth;
public BinaryTree<T> Next;
public BinaryTree(T data) : base(data)
{
}
}
class Solution
{
static void Main(string[] args)
{
for (var i = 0; i < 5; i++)
{
Console.WriteLine("Hello, World");
}
BinaryTree<string> oRoot = InitString();
Queue<BinaryTree<string>> que = new Queue<BinaryTree<string>>();
que.Enqueue(oRoot);
int depth = 0;
oRoot.Depth = 0;
BinaryTree<string> tempPrevious = null;
bool b = false;
while(que.Count > 0)
{
b = false;
BinaryTree<string> node = que.Dequeue();
if(tempPrevious != null )
{
if( tempPrevious.Depth == node.Depth)
{
tempPrevious.Next = node;
Console.Write(tempPrevious.Data + "--> " );
}
else
{
tempPrevious.Next = null;
Console.WriteLine(tempPrevious.Data + "--> NULL");
}
}
if(node.Left != null)
{
node.Left.Depth = node.Depth + 1;
que.Enqueue(node.Left);
b = true;
}
if(node.Right != null)
{
node.Right.Depth = node.Depth+1;
que.Enqueue(node.Right);
b = true;
}
if(que.Count == 0 )
{
Console.WriteLine(node.Data + "--> NULL");
}
tempPrevious = node;
}
}
static BinaryTree<int> Init()
{
BinaryTree<int> root = new BinaryTree<int>(5);
root.Left = new BinaryTree<int>(1);
root.Right = new BinaryTree<int>(10);
root.Left.Left = new BinaryTree<int>(2);
root.Left.Right = new BinaryTree<int>(4);
root.Right.Left = new BinaryTree<int>(3);
root.Right.Right = new BinaryTree<int>(8);
return root;
}
static BinaryTree<string> InitString()
{
BinaryTree<string> root = new BinaryTree<string>("CVS");
root.Left = new BinaryTree<string>("Anu");
root.Right = new BinaryTree<string>("Tanu");
root.Left.Left = new BinaryTree<string>("Reyansh");
root.Right.Left = new BinaryTree<string>("Saisha");
root.Right.Right = new BinaryTree<string>("Shaurya");
return root;
}
}
using System;
using System.Collections.Generic;
// To execute C#, please define "static void Main" on a class
// named Solution.
public class Node<T>
{
public T Data;
public Node(T data)
{
Data=data;
}
}
public class BinaryTree<T> : Node<T>
{
public BinaryTree<T> Left;
public BinaryTree<T> Right;
public int Depth;
public BinaryTree<T> Next;
public BinaryTree(T data) : base(data)
{
}
}
class Solution
{
static void Main(string[] args)
{
for (var i = 0; i < 5; i++)
{
Console.WriteLine("Hello, World");
}
BinaryTree<string> oRoot = InitString();
Queue<BinaryTree<string>> que = new Queue<BinaryTree<string>>();
que.Enqueue(oRoot);
int depth = 0;
oRoot.Depth = 0;
BinaryTree<string> tempPrevious = null;
bool b = false;
while(que.Count > 0)
{
b = false;
BinaryTree<string> node = que.Dequeue();
if(tempPrevious != null )
{
if( tempPrevious.Depth == node.Depth)
{
tempPrevious.Next = node;
Console.Write(tempPrevious.Data + "--> " );
}
else
{
tempPrevious.Next = null;
Console.WriteLine(tempPrevious.Data + "--> NULL");
}
}
if(node.Left != null)
{
node.Left.Depth = node.Depth + 1;
que.Enqueue(node.Left);
b = true;
}
if(node.Right != null)
{
node.Right.Depth = node.Depth+1;
que.Enqueue(node.Right);
b = true;
}
if(que.Count == 0 )
{
Console.WriteLine(node.Data + "--> NULL");
}
tempPrevious = node;
}
}
static BinaryTree<int> Init()
{
BinaryTree<int> root = new BinaryTree<int>(5);
root.Left = new BinaryTree<int>(1);
root.Right = new BinaryTree<int>(10);
root.Left.Left = new BinaryTree<int>(2);
root.Left.Right = new BinaryTree<int>(4);
root.Right.Left = new BinaryTree<int>(3);
root.Right.Right = new BinaryTree<int>(8);
return root;
}
static BinaryTree<string> InitString()
{
BinaryTree<string> root = new BinaryTree<string>("CVS");
root.Left = new BinaryTree<string>("Anu");
root.Right = new BinaryTree<string>("Tanu");
root.Left.Left = new BinaryTree<string>("Reyansh");
root.Right.Left = new BinaryTree<string>("Saisha");
root.Right.Right = new BinaryTree<string>("Shaurya");
return root;
}
}
def add_next(tree):
q = []
q.append((tree, 0))
while q:
node_tuple = q.pop(0)
if not q or q[0][1] != node_tuple[1]:
node_tuple[0].next = None
else:
node_tuple[0].next = q[0][0].data
level = node_tuple[1] + 1
if node_tuple[0].left:
q.append((node_tuple[0].left, level))
if node_tuple[0].right:
q.append((node_tuple[0].right, level))
return tree
def add_next(tree):
q = []
q.append((tree, 0))
while q:
node_tuple = q.pop(0)
if not q or q[0][1] != node_tuple[1]:
node_tuple[0].next = None
else:
node_tuple[0].next = q[0][0].data
level = node_tuple[1] + 1
if node_tuple[0].left:
q.append((node_tuple[0].left, level))
if node_tuple[0].right:
q.append((node_tuple[0].right, level))
return tree
Here is C++ version of the solution
#include<list>
using namespace std;
struct Node {
Node * left;
Node * right;
Node * next;
Node():left(0),right(0),next(0){}
};
void link_nodes(Node* s)
{
list<Node*> queue;
Node* last_node = nullptr;
int nodes_to_process = 0, next_level_nodes = 0;
queue.push_back(s);
nodes_to_process = 1;
while (queue.size()>0)
{
Node* cur = queue.front();
queue.pop_front();
nodes_to_process--;
if (cur->left)
{
queue.push_back(cur->left);
next_level_nodes++;
}
if (cur->right)
{
queue.push_back(cur->right);
next_level_nodes++;
}
if (last_node)
last_node->next = cur;
if (nodes_to_process > 0)
{// this is next level
last_node = cur;
} else {
//this is next level
nodes_to_process = next_level_nodes;
next_level_nodes = 0;
last_node = 0;
}
}
}
1. Insert same level node in a list, from left to right.
2. iterate the list and assign the element[i].next = element[i+1], the last element's next should be null
3. go down to the next level and repeat 1.
public void PopulateNext(Node node)
{
List<Node> listNodes = new ArrayList<Node>();
node.next = null;
listNodes.add(node);
while(listNodes.size() > 0)
{
List<Node> newListNodes = new ArrayList<Node>();
for(int i=0;i<listNodes.size()-1;i++)
{
listNodes.get(i).next = listNodes.get(i+1);
if(listNodes.get(i).left != null)
newListNodes.add(listNodes.get(i).left);
if(listNodes.get(i).right != null)
newListNodes.add(listNodes.get(i).right);
}
Node mostRightNode = listNode.get(listNodes.size()-1);
mostRightNode.next = null;
if(mostRightNode.left != null)
newListNodes.add(mostRightNode.left);
if(mostRightNode.right != null)
newListNodes.add(mostRightNode.right);
listNodes = newListNodes;
}
}
void ConnectNexts(Node* root)
{
if (root == nullptr || (!root->left && !root->right))
{
return;
}
if (root->left)
{
root->left->next = root->right;
}
if (root->next)
{
Node* newNextNode = root->next->left ? root->next->left : root->next->right;
if (root->right)
{
root->right->next = newNextNode;
}
else
{
// At this point root->left should exist
root->right->next = newNextNode;
}
}
ConnectNexts(root->left);
ConnectNexts(root->right);
}
This is just a variation of Breadth First traversal on a tree.
- romil.bm April 17, 2015void setNextNode(Node root) { Queue<Node> mainQueue = new ArrayDequeue<Node>(); if (root == null) return; mainQueue.add(root); int nodesInCycle = 1; while (!mainQueue.isEmpty()) { Queue<Node> holdingQueue = new ArrayDequeue<Node>(); for (int i = 0; i < nodesInCycle; i++) { Node current = mainQueue.remove(); current.next = mainQueue.peek(); if (current.left != null) holdingQueue.add(current.left); if (current.right != null) holdingQueue.add(current.right); } mainQueue.addAll(holdingQueue); nodesInCycle = mainQueue.size(); } }