Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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);
}
How about this ?
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?
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;
}
}
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;
}
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;
}
}
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;
}
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);
}
}
}
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;
}
}
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;
}
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;
}
}
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 add_position = 0;
int remain = n;
curr = this;
while (curr != NULL) {
stack[add_position] = curr;
curr = curr->left;
if (stack_items < n) {
stack_items++;
}
add_position = (add_position + 1) % n;
}
curr = NULL;
while (remain != 0 && stack_items != 0) {
/* POP */
--add_position;
--stack_items;
if (add_position < 0) {
add_position += n;
}
curr = stack[add_position];
if (--remain == 0) { // visiting current.
break;
}
curr = curr->right;
while (curr != NULL) {
stack[add_position] = curr;
curr = curr->left;
if (stack_items < n) {
stack_items++;
}
add_position = (add_position + 1) % n;
}
}
free(stack);
return curr;
}
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)
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;
}
}
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)
}
- remlostime November 26, 2012