Facebook

  www.facebook.com
  www.facebook.com

Interview Question

Software Engineer, Infrastructure Interview Menlo Park, CA

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
Answer

Interview Answer

7 Answers

0

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

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

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

//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

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

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

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.