Interview Question

Software Engineer Interview

How do you find the kth smallest number in a binary search

  tree.
Answer

Interview Answer

3 Answers

0

A brute force approach would be to put all the left children in an array and then look for kth element of this array.

Lucas on May 28, 2014
3

Inorder traversal the tree, the returned array is sorted, then find the Kth smallest number. O(n)time and O(n)space.Anyone has better idea?

Anonymous on May 31, 2014
2

Inorder traversal, but count the number of the nodes you visted, because the visiting order will just be increasing,so O(lgn) time to find the smallest node and O(1) space to store counter.

Anonymous on Jun 9, 2014

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up