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.

Question

Meena · Accepted Answer

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

double'o · Answer

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;

        }

Sigiloso · Answer

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; }
}

Bunny ShaveDog · Answer

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);
}

xx · Answer

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);
}

anon · Answer

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;
}

brian · Answer

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

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas