6
$\begingroup$

I was wondering for some time how to approach a situation like the following one. Imagine a standard binary tree data structure with $n$ nodes in it. Each node contains pointers to its left and right children, and from that node we can navigate to each of these children in constant time.

We are looking to find whether an algorithm with given requirements exists, or not. In case there is such an algorithm, we should be able to come up with one. In case such an algorithm does not exist, I am very much interested in how to formally prove that. Most impossibility results I've come across usually rely on reduction to other problems which are known to be not solvable (like general purpose comparison-based sorting in time, asymptotically faster than $O(n\log n)$) or using some sort of decision tree argument directly.

However, in this particular case I am completely stuck both in ideas, and in a much more fundamental way: how to formally state some of the requirements.

Let's move on to the problem.

Condition 1: The algorithm should visit each node of the tree once, in other words, it is a traversal algorithm. We don't care about the order of the traversal: in-order, post-order, level-order, etc. Any order, even a completely random one and/or non-deterministic one, will do.

Condition 2: The time complexity of the algorithm should be $O(n)$. Clearly an optimal one.

Condition 3: The space complexity of the algorithm should be $O(1)$.

Condition 4: The tree is read-only, it should not be modified during the traversal.

Condition 5: The tree structure does not contain pointers from each node to its parent. In other words, we cannot assume that there exists a pre-built lookup table or any other mechanism that allows us to jump from a node to its parent in constant time.

Let's now consider following questions:

Q1: Does there exist an algorithm that satisfies all of Cond1, Cond2, Cond3, Cond5?

A1: Yes, one example is the well-known Morris traversal. Please note that it violates Cond4.

Q2: Does there exist an algorithm that satisfies all of Cond1, Cond2, Cond3, Cond4?

A2: Yes, one example is the classical in-order traversal by navigating to the smallest node in the tree (if we imagine it to be a BST), and then repeatedly moving to the successor while it is not $null$. This, however, heavily relies on parent pointers. There are other solutions too, again exploiting parent pointers. In other words, all approaches known to me violate Cond5.

Q3: Does there exist an algorithm that satisfies all of Cond1, Cond2, Cond3, Cond4, Cond5?

A3: I don't know!

My personal conjecture is that such an algorithm does not exist. However, I am totally stuck as to how to approach proving that. I've taken some classical Computational Complexity classes in my MSc studies that teach Turing machines results and theorems, but my major problem here is:

  • how to even formally state Cond4 and Cond5 under the Turing machines model, or any other standard computational formalism? Obviously these conditions are necessary for the (supposedly) negative result, since if we relax any one of them, the answer becomes affirmative, as shown by Q1 and Q2.

Has anyone else explored formally this topic before? I am really interested in a formal rigorous proof.

Please note that I am contemplating on this problem only because of personal interest and curiosity. It is not related to any studies, homework, exams, contests, etc.

$\endgroup$
14
  • 1
    $\begingroup$ (See also: Can a tree be traversed cheaply?) $\endgroup$ – greybeard Sep 4 '20 at 7:33
  • $\begingroup$ The standard model of space-bounded computation already includes Condition 4 (since the input tape is read only). Condition 5 just specified how the input is given. So it's easy to formalize it as a complexity question. Note that your $O(1)$ space in Condition 3 is actually logarithmic space in the Turing machine model. $\endgroup$ – Yuval Filmus Sep 5 '20 at 6:08
  • $\begingroup$ I think it's better to consider a simpler question first: count the number of nodes in the tree. $\endgroup$ – Dmitry Sep 5 '20 at 6:18
  • $\begingroup$ @HungryKoala Well note if you try to model this problem with a Turing Machine (e.g. like Dimitry proposed by counting the nodes) you would need to encode your tree as a input string. This string would contain all the information for every node. The Turing Machine could just go over the string node by node in linear time instead of using pointers (basically a chaotic traversal). Thus in the TM model there is a algo satisfying all conditions for the node counting problem. $\endgroup$ – plshelp Sep 5 '20 at 14:05
  • $\begingroup$ You could create another model of computation where the algorithm can only use the pointers but that wouldn't be the TM model anymore. $\endgroup$ – plshelp Sep 5 '20 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.