## Yahoo Interview Question Software Engineer / Developers

• 0

Write a function that returns a node in a tree given two parameters: pointer to the root node and
the inorder traversal number of the node we want to return. The only information stored in the tree is
the number of children for each node

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````Node * KthSmallest(Node *n, int k)
{
int leftCount;
if (n->pLeft == NULL)
leftCount = 0;
else
leftCount = n->pLeft->count;

if (leftCount + 1 == k) return n;
if (leftCount + 1 < k) return KthSmallest(n->pRight, k - 1 - leftCount);
return KthSmallest(n->pLeft, k);
}``````

In main() call

``Node *pSolution = KthSmallest(pRoot, inOrderNumber);``

Comment hidden because of low score. Click to expand.
0
of 0 vote

There is really no point for recursion here. I think that using recursion at these places is actually not a good practice. Though on a similar lines using iteration, this code looks more efficient to me:

``````Nodeptr nthInInorder(Nodeptr root, int x){
Nodeptr curr = root;
int countedIn = 0, leftchildren = 0, currIn=0;

while(curr!=NULL){
if(curr->left == NULL)
leftchildren = 0;
else
leftchildren = (curr->left)->data + 1;

currIn = countedIn + leftchildren + 1;

if(currIn == x)
return curr;
else if(currIn > x)
curr = curr->left;
else if(currIn < x)
{ countedIn = currIn + 1;
curr = curr->right;
}
}
return NULL;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.