Google Interview Question
Software Engineer / DevelopersReverse 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