0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ It is not possible to traverse a BST without a stack, unless you use a destructive method (i.e. that modifies the links, possibly in an irreversible way). Is that allowed ? Check "Morris Traversal". $\endgroup$
    – user16034
    Commented Mar 13, 2023 at 13:16

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – user183748292
    Commented Jun 19, 2021 at 14:12
  • $\begingroup$ (I think successor/predecessor is amortised constant time. But without parent information in each and every node, I don't see constant additional space.) $\endgroup$
    – greybeard
    Commented Jun 19, 2021 at 14:39
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Commented Jun 19, 2021 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.