Work in HR? Unlock Free Profile

Facebook Software Engineer Interview Question

"How do you find the kth smallest number in a binary search tree."
Add Tags [?]

Part of a Software Engineer Interview Review - one of 1,068 Facebook Interview Reviews

Answers & Comments

of 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
of 2
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
of 1
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

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

Tags are like keywords that help categorize interview questions that have something in common.