Timeline for Find kth smallest element in binary search tree
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 3, 2018 at 22:54 | comment | added | AJNeufeld |
How is TreeNode defined? If it contains the size of the subtree, you can solve the problem in O(1) space, O(log k) time (average), O(k) time worst case.
|
|
| Nov 29, 2018 at 20:45 | comment | added | greybeard | (Originally asked in SO.) | |
| Nov 29, 2018 at 19:58 | comment | added | greybeard |
(Following proper specification and comments,) I guess I'd a) try to get hands on a capacity limited Deque b) push a dummy "super root" sr (root.clone()?) with sr.right = root, increase k and get rid of the duplicated push left-path.
|
|
| Nov 29, 2018 at 16:08 | comment | added | vnp | If it is mutable, the Morris traversal is an answer. | |
| Nov 29, 2018 at 9:04 | answer | added | Peter Taylor | timeline score: 1 | |
| Nov 29, 2018 at 8:11 | answer | added | mtj | timeline score: 2 | |
| Nov 29, 2018 at 7:01 | history | edited | 200_success | CC BY-SA 4.0 |
added 5 characters in body; edited tags; edited title
|
| Nov 29, 2018 at 6:42 | comment | added | user33306 |
Do you have control over the TreeNode class?
|
|
| Nov 29, 2018 at 5:57 | comment | added | user5447339 | I didn't asked this question to the interviewer but let's say if it is not mutable then can we optimize anything? And let's say if it is mutable then how efficiently we can do it? | |
| Nov 29, 2018 at 5:36 | comment | added | vnp |
Is the tree mutable? Is O(k) memory acceptable?
|
|
| Nov 29, 2018 at 5:20 | history | asked | user5447339 | CC BY-SA 4.0 |