## Google Interview Question

Software Engineer / Developers```
Reverse of Inorder Traversal :
Rev_Inorder( Tree* T ,int c ,int N )
{
if( T==Null )return;
Rev_Inorder( T->right );
Rev_Inorder( T->left );
c++;
if(c== N)
print( T->data );
}
Call : Rev_Inorder( T , 0 , N );
```

problems with recursive calls as well

nevertheless, not the correct solution..the counter c increases from top-down..i would guess it should happen bottom-up..for the largest element would be at the right most bottom

whereas in this case, the counter would invariably reach N at nth level from the root

Rev_Inorder(Node* node, int& counter, int N)

{

if(node == null)return;

Rev_Inorder(node->right);

if(counter == N)

{

return;

}

count++;

print root->data;

Rev_Inorder(node->left);

}

Call: Rev_Inorder(root, 0, N)

The call will print the largest N number. Should be return after add the count, otherwise, the whole tree will be travasal

Node* findNth(Node* tree, int& N)

{

if(n < 0 || tree == NULL) return NULL;

if(n == 0) return tree;

Node* rightRes = findNth(tree->right, n);

if(n <= 0) return rightRes;

if(n == 1) return tree;

return findNth(tree->left, n);

}

Each node has two counts: numLeft and numRight denoting number of nodes in its left and right subtrees respectively.

Node& getTheNode(const Node& curr, int N)

{

if(curr.numRight == N-1)

return curr;

else if(curr.numRight > N-1)

return getTheNode(curr.rightChild,N);

else // if(curr.numRight > N-1)

return getTheNode(curr.leftChild,N-1-curr.numRight);

}

O(log n) where n is the number of elements in the BST.

Each node has two counts: numLeft and numRight denoting number of nodes in its left and right subtrees respectively.

Node& getTheNode(const Node& curr, int N)

{

if(curr.numRight == N-1)

return curr;

else if(curr.numRight > N-1)

return getTheNode(curr.rightChild,N);

else // if(curr.numRight > N-1)

return getTheNode(curr.leftChild,N-1-curr.numRight);

}

O(log n) where n is the number of elements in the BST.

Not sure it's optimal:

1) get the smallest node in the tree (leftmost node)

2) call successor on the smallest node for n-1 times

Not sure about the time complexity, but might be better than 0(logn)

- Somendra Raj March 09, 2019