# 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

We can do this in $$\theta(n^2)$$ time if we calculate the average of all couples of nodes in the tree and compare it to the root, but this is too much time.

We can do this in linear time but with extra space by saving the in-order traversal of the left sub tree to array A, and the right sub tree to array B.

Now for the first node in A, scan B, until we find the matching node in B, or until we reach a too large element in B save that index as $$k$$.

If it is the second case, iterate over the rest of A and for each node:

Traverse B backwards from index $$k-1$$ until we find the matching node, or, if we reached a node that is too small, save the index as $$k-2$$ and repeat.

This takes $$\theta(n)$$ time but is using extra space. How can we do this in $$\theta(n)$$ and without extra space?

## 1 Answer

Your idea using the in-order traversal is good. Instead of constructing the in-order traversal, you can just traverse and get the element you currently need. That means you wont construct the full output of the in-order traversal, but instead you will get only one item at a time from that traversal, when you need it.

• 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 at 14:12
• (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 at 14:39
• 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 at 14:43