Facebook

  www.facebook.com
Work in HR? Unlock Free Profile

Facebook Software Engineer, Infrastructure Interview Question

I interviewed in Menlo Park, CA and was asked:
"Write a function that takes 2 arguments: a binary tree and an integer n, it should return the n-th element in the inorder traversal of the binary tree."
Tags: coding binary tree
Add Tags [?]
Answer

Part of a Software Engineer, Infrastructure Interview Review - one of 1,089 Facebook Interview Reviews

Answers & Comments

0
of 2
votes

Correct answer should be something like this:

int FindNthElement(Node *node, int &n)
{ if (node->Left && n > 0)
      { k = FindNthElement(node->left, n);
          if (n == 0) return k; }
   if (n == 0) return node->value;
   else if (n > 0 && node->right)
       { k = FindNthElement(node->right, n);
           if (n == 0) return k;
          else return -1; }
}

- Interview Candidate on Aug 5, 2012
0
of 1
vote

int findNthElementByInorder(Node *node, int &n)
{
    if (node == null)
        return -1;
    findNthElementByInorder(node->left, n);
    if (n == 0)
        return node-> value;
    else
       n--;
   findNthElementByInorder(node->right, n);
}

- xx on Aug 10, 2012
0
of 1
vote

Seems it should be something like this, get the to bottom and start counting up from there.

int start(Node *node, int &n)
{
    int element = 0;

    if (node == null)
        return -1;

   return findElementIndex(node, element, n);
}

int findElementIndex(Node *node, int &currentNumber, int findNumber) {

    if(node->left != null ) {
            int result = findElementIndex(node->left, currentNumber, findNumber);

        if(result != -1)
          return result;
       }

    if(node->right != null ) {
            int result = findElementIndex(node->right, currentNumber, findNumber);

        if(result != -1)
          return result;
       }

    currentNumber++;
    if(currentNumber == findNumber)
        return node->value;

    else
        return -1;
}

- anon on Aug 22, 2012
0
of 1
vote

//Assumption is that the node values are not negative.
//If the tree has less than n nodes, -1 will be returned.

int findNthElementByInorder(Node *node, int &n)
{
    if ((node != null) && (n > 0))
    {
        findNthElemetnByInorder(node>left, n);
        n--; //Count the current node
        findNthElemetnByInorder(node>right, n);

        return node->value;
    }
    else
        return -1;
}

- brian on Oct 7, 2012
2
of 2
votes

def nth_inorder_node(treeNode, counter)
  # Check left node
  if treeNode.left
    rv = nth_inorder_node(treeNode.left, counter)
    return rv if rv
  end

  # Check current node
  counter.value -= 1
  puts "counter: #{counter.value} \t node: #{treeNode.data}".green
  return treeNode.data if counter.value == 0

  # Check right node
  if treeNode.right
    rv = nth_inorder_node(treeNode.right, counter)
    return rv if rv
  end

  return nil
end

- Meena on Oct 11, 2012
2
of 3
votes

int nthelement(Node node, int n){
        int ret;
                if( node.left != null)
                { ret = nthelement(node.left, n);

                        if(ret != -1)
                                return ret;
                }

                n --;
                if(n ==0)
                        return node.data;

                if(node.right != null)
                {
                        ret = nthelement(node.right, n);

                        if(ret!= -1)
                                return ret;
                }
        return -1;

        }

- double'o on Oct 19, 2012
0
of 0
votes

int [] results;
int count = 0;

int returnNthElement(Node rootNode, int element) {
    fillArray(rootNode);
    return results[element];
}

void fillArray(Node node) {
    if (node == null) {
        return null;
    }
    if (node.left == null && node.right == null) {
        count++;
        results[count] = node;
        return;
    }
    fillArray(node.left);
    count ++;
    results[count] = node;
    fillArray(node.right);
}

- Bunny ShaveDog on Jan 12, 2013

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.