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

## Interview Answer

7 Answers

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

}

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 ¤tNumber, 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;

}

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

}

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

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;

}

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

}

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

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

}