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

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