Timeline for Find two nodes in a BST such that the root's key is the average of their keys without extra space in $\theta(n)$ worst case time
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 19, 2021 at 14:43 | comment | added | nir shahar | Try to think of it as running the in-order traversal algorithm, but in "chunks", where sometimes you stop to do something else. The basic key idea that makes it $O(n)$ is that you never traverse through a node more than twice. | |
| Jun 19, 2021 at 14:39 | comment | added | greybeard | (I think successor/predecessor is amortised constant time. But without parent information in each and every node, I don't see constant additional space.) | |
| Jun 19, 2021 at 14:12 | comment | added | user183748292 | Thanks, I tried this approach but traversing it one by one means find successor/predecessor which takes $\theta(h)$ for each time I'm looking for the next/previous in the in-order traversal, or at least this is the best I came up with. Not sure how we can do these steps in $\theta(1)$ without having the entire scan saved in extra space. | |
| Jun 19, 2021 at 13:52 | history | answered | nir shahar | CC BY-SA 4.0 |