## Facebook Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````Node *findElement(Node *root, int n, int &num)
{
if (root == NULL)
return NULL;

Node *left = findElement(root->left, n, num);
if (left != NULL)
return left;

num++;
if (n == num)
return root;

Node *right = findElement(root->right, n, num);

return right;
}``````

Comment hidden because of low score. Click to expand.
0

If you decrease the counter instead of increasing it then only one variable suffices. Otherwise great solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````code submitted:
public  class Result {
Node foundNode;
int iteration;
}

public  class Node {
int value;
Node left;
Node right;

public Node(int value) {
this.value = value;
}

}

public  void findNth(final Node node, int N, final Result result) {
if (node.left != null && result.foundNode == null) {
findNth(node.left, N, result);
}

// handle root
result.iteration++;

if (result.iteration == N) {
result.foundNode = node;

return;
}

if (node.right != null && result.foundNode == null) {
findNth(node.right, N, result);
}``````

Comment hidden because of low score. Click to expand.
0

Was it accepted ?

Comment hidden because of low score. Click to expand.
0

Most probably; seems legit.

Comment hidden because of low score. Click to expand.
0
of 0 vote

inorder traversal of a binary tree prints elements in a sorted order .

So we can have a method that takes two arguments :the binary tree as an array and the integer n . Sort the the elements and output the Nth element in it?

Comment hidden because of low score. Click to expand.
0

Why should we make it so complex of introducing sorting (O(n log n)) ? just do inorder traversal (O(n)) keeping a counter and print the element or return when your counter == N.

Comment hidden because of low score. Click to expand.
0
of 0 vote

node* findNthElementInorder(node *root,int n)
{
static int a;
static struct node *nthelement=NULL;

if(root==NULL)
return NULL;
if(nthelement==NULL)
{
nthelement=findNthElementInorder(root->left,n);
a++;
if(a==n)
return root;
nthelement=findNthElementInorder(root->right,n);
}
else
{
return nthelement;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

use morris inorder traversal to get the required answer

or just use recursion

Comment hidden because of low score. Click to expand.
0
of 0 vote

Untested recursive method

``````Tree *find(Tree *root, int n) {
Tree *node
int num = find(root, &node);
if (num >= n) {
return node;
}
return NULL;
}

int find(Tree * root,  int n, Tree ** needle) {

if (!root) return 0;

int num_left = find(root->right, n, needle);

// Found in left subtree
if (num_left >= n) return num_left;

// The root is what we require
if (num_left == n-1)  {*out  = root;  return n}

int num_right = find(root->right, n-num_left, out);
return num_right + 1 + num_left;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

void fun(tnode root,int n){
if(root!=NULL){
if(n==1){
printf("%d",root->data);return;
}
else{
fun(root->left,n-1);
fun(root->right,n-1);
}
}
else{
printf("error");
return;
}
}

Comment hidden because of low score. Click to expand.
0

completely left skewed tree will fail your code
consider
7 6 5 4 3 2 1 (left skewed tree) and n = 2
call on 6 with 1 and print 6 which is wrong answer.

you seem to be following preorder traversal.

Try to modify it to inorder.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Tree is in ascending inorder traversal.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a solution in java. The hard part of this algorithm is communicating the count of visited nodes between recursive calls. It would be trivial if there was some out-of-scope variable, but that is ugly and not needed. Java is pass by value, so using the primitive java int does not retain its value between recursive calls, however an Integer object wrapper will, because all we are doing is passing a copy of the reference to the integer object, which any recursive call can mutate.

``````Node findNthInOrderNode(Node root, Integer n){
if(n < 0){ throw new IllegalArgumentException(); }
if(root != null){
Node left = findNthInOderNode(root.left(), n);
if(left != null){ return left; }
if(n == 0){ return root; }
n--;
Node right = findNthInOrderNode(root.right, n);
if(right != null){ return right; }
}
return null;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void findNthElementInorder(struct TNode* node,int N, int& count, struct TNode*& nthNode)
{
assert(N>=0);
if(node && count!=N) {
if(nthNode==NULL) {
findNthElementInorder(node->left, N, count, nthNode);

// PROCESSED ONE ELEMENT INCREMENT THE COUNT
count++;
if(count==N) { nthNode = node; return; }

findNthElementInorder(node->right, N, count, nthNode);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Node* f(Node* r, int *n)
{
if(*n<0 || r==null)
return null;

if(*n==0)
return r;

Node* t = f(r->left, n);
if(t)
return t;

if(*n==0)
return r;

*n = (*n)-1;
return f(r->right, n);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here I am assuming that the answer can be stored in an argument variable passed into the input.

``````int func(Node* temp,int N,Node* ans = NULL){
if(temp==NULL)
return 0;
else{
int ct = func(temp->left,N,ans);
if(ct >= N)
return N;
ct++;
if(N-ct==0){
ans = temp;
return N;
}
ct += func(temp->right,N-ct,ans);
if(ct >= N)
return N;
return ct;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

int inorderN(node * x, int &N)
{
if(N <=0)
error(‘N must be positive!’);
if(x==Null)
return -1;
N = N - 1;
if (N == 0)
return x->key;
int s = inorderN(x->left,N);
if (N == 0)
return s;
s = inorderN(x-right,N);
if (N == 0）
return s;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is perfect for iterative inorder traversal which maintains the function signature and computes the function easily.

private static TreeNode findNthInOrderIterative(TreeNode root, int n) {
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode curr = root;
boolean done = false;
while (!done) {
if (curr != null) {
s.push(curr);
curr = curr.left;
}
else {
if(!s.empty()) {
curr = s.pop();
n--;
if(n == 0) {
return curr;
}
curr = curr.right;
}
else {
done = true;
}
}
}
System.out.println("Couldn't find element...returning the tree root");
return root;
}

Comment hidden because of low score. Click to expand.
0

Good approach but one minor mistake. You should have pushed root.right to stack as well after visit root.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Use modified recursive inorder

modified_inorder(node *pt,int n)
{
if(pt!=NULL)
{
modified_inorder(pt->left,n);
n--;
if(n==0)
cout << pt->info<<endl;
modified_inorder(pt->right,n);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

void nthElement(Node *node, int &n, int &key)
{
if (node == NULL)
{
return;
}

nthElement(node->left, n, key);
n--;
if (n == 0)
{
key = node->v;
return;
}
nthElement(node->right, n, key);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Node *
Findnth( node * root, int n)
{
Stack<node *> stack;

While (root != null){
Stack.push(root);
Root = root.left;
}

While (!stack.empty() && n != 0)) {
Root = stack.top();
Stack.pop();
N--; // a node is getting visited.
If ( n == 0) return root;
// this node's left sub tree has been visited already, it itself has been visited as well. Now we need to concentrate on its right sub tree.
Root = root->right;
While (root != null) {
Stack.push(root);
Root = root->left;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

memory O(n) and iterative. computation complexity equivalent to in order traversal.

#include <stdio.h>
#include <malloc.h>

class BinaryTreeNode
{
private:
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;

public:
BinaryTreeNode *FindNthInOrderNode(int n);
};
BinaryTreeNode *
BinaryTreeNode::FindNthInOrderNode(int n)
{
BinaryTreeNode **stack = (BinaryTreeNode **)malloc(n* sizeof(BinaryTreeNode *));
BinaryTreeNode *curr;
int stack_items = 0;
int remain = n;

curr = this;
while (curr != NULL) {
curr = curr->left;
if (stack_items < n) {
stack_items++;
}
}

curr = NULL;
while (remain != 0 && stack_items != 0) {
/* POP */
--stack_items;
}
if (--remain == 0) { // visiting current.
break;
}
curr = curr->right;
while (curr != NULL) {
curr = curr->left;
if (stack_items < n) {
stack_items++;
}
}
}

free(stack);
return curr;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def inorder_n( x, n )
return 0,nil if x.nil?

left,node = inorder_n( x.left, n )
return left+1, node unless node.nil?
n -= left

return left+2,x if n == 0
n -= 1

right,node = inorder_n( x.right, n )
return right+1, node unless node.nil?
n -= right

return n,nil
end

_,node = inorder_n( root, n)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

morris inorder traversal.

``````TreeNode * InOrder(TreeNode * root, int n) {
int cnt = 0;
TreeNode * rs = NULL;
while (root != NULL) {
if (root->left != NULL) {
cnt++;
if (cnt == n) rs = root;
root = root->left;
} else {
TreeNode * tmp = root->left;
while (tmp->right != NULL && tmp->right != root) tmp = tmp->right;
if (tmp->right == NULL) {
tmp->right = root;
root = root->left;
} else {
cnt++;
if (cnt == n) rs = root;
tmp->right = NULL;
root = root->right;
}
}
}
return rs;
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution with Swift.

/**
A function that takes 1 argument an integer N, it should return the N-th element in the inorder traversal of the binary tree.

- parameter n: The N-th element
*/

func findElement(n: Int) -> T? {

var num = n
return findElementHelper(root, n: &num)
}

private func findElementHelper(node: TreeNode<T>?, inout n: Int) -> T? {

guard let node = node else {
return nil
}

if let element = findElementHelper(node.left, n: &n) {
return element
}

if n == 0 {
return node.data
} else {
n = n-1
}

return findElementHelper(node.right, n: &n)
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.