14
$\begingroup$

Half a decade ago I was sitting in a data structures class where the professor offered extra credit if anyone could traverse a tree without using recursion, a stack, queue, etc. (or any other similar data structures) and just a few pointers. I came up with what I thought was an obvious answer to that question which was ultimately accepted by the professor. I was sitting in a discrete math class with another professor in the same department--and he asserted that it was impossible to traverse a tree without recursion, a stack, queue, etc., and that my solution was invalid.

So, is it possible, or impossible? Why or why not?

Edit: To add some clarification, I implemented this on a binary tree which had three elements-- the data stored at each node and pointers to two children. My solution could be extended to n-ary trees with only a few changes.

My data structures teacher did not put any constraints against mutating the tree, and indeed I found out later that his own solution was to use the child pointers to point back up the tree on his way down. My discrete math professor said any mutation of a tree means that it is no longer a tree according to the mathematical definition of a tree, his definition would also preclude any pointers to parents--which would match the case where I solved it above.

$\endgroup$
  • 3
    $\begingroup$ You need to specify the constraints. Am I allowed to mutate the tree? How is the tree represented? (For instance, does each node have a parent pointer to its parent?) The answer will depend upon the specific constraints; without specifying those constraints, this is not a well-posed problem. $\endgroup$ – D.W. Nov 9 '13 at 3:43
  • 2
    $\begingroup$ I guess the contraint the professors really wanted to express was "with $O(1)$ additional space". But what was your solution, anyway? $\endgroup$ – Raphael Nov 9 '13 at 15:12
16
$\begingroup$

A lot of research in this area has been dome, motivated by method of "cheaply" traversing trees and general list structures in the context of garbage collection.

A threaded binary tree is an adapted representation of binary trees where some nil-pointers are used to link to successor nodes in the tree. This extra information can be used to traverse a tree without stack. However, an extra bit per node is necessary to distinguish threads from child-pointers. Wikipedia:Tree_traversal

As far as I know binary trees implemented using pointers in the usual fashion (left and right pointer per node) can be traversed using the method of threads, in a method attributed to Morris. The NIL-pointers are temporarily re-used to thread a path back to the root. The clever part is that during traversal one can distinguish the original edges from the temporary thread-links, using the way they form cycles in the tree).

Good part: no extra data structure. Bad part: slightly cheating, the stack is inside the tree in a clever way. Very clever.

A proof of the hidden stack is shown in P. Mateti and R. Manghirmalani: Morris's Tree Traversal Algorithm Reconsidered DOI:10.1016/0167-6423(88)90063-9

J.M. Morris: Traversing binary trees simply and cheaply. IPL 9 (1979) 197-200 DOI:10.1016/0020-0190(79)90068-1

Then there also is Lindstrom scanning. This method "rotates" the three pointers involved in each node (parent and two children). If you want to perform any decent pre-order or post-order algorithms you need extra bits per node. If you just want to visit all the nodes (three times, but you never know which visit you perform) then it can be done without the bits.

G. Lindstrom: Scanning list structures without stacks or tag bits. IPL 2 (1973) 47-51. DOI:10.1016/0020-0190(73)90012-4

Perhaps the most straightforward way is a method by Robson. Here the stack needed for the classic algorithm is threaded through the leaves.

J.M. Robson: An improved algorithm for traversing binary trees without auxiliary stack IPL 1 (1973) 149-152. 10.1016/0020-0190(73)90018-5

IPL = Information Processing Letters

$\endgroup$
  • $\begingroup$ I like this solution too, though it's nothing that I would have come up with during my first year of computer science classes. Yeah, probably cheating according to my professor's rules. $\endgroup$ – Nathan L Nov 8 '13 at 22:39
  • 2
    $\begingroup$ Can you give links/references for the strategies? $\endgroup$ – Raphael Nov 9 '13 at 15:13
  • 1
    $\begingroup$ The real bad part with that method is that you can't have more than one traversal going on at any one time. $\endgroup$ – Gilles Nov 14 '13 at 13:28
6
$\begingroup$

I suppose that each node has a pointer to its parent (unless it's the root), as well as to its first child (if any), and its child has a pointer to its next sibling (if any). You can now simulate your favorite traversal order. You just need to come up with a rule of selecting the next node. For example, suppose you want to simulate postorder. Your first node is the "leftmost descendant", which can be obtained by starting at the root, and repeatedly moving to the first child. Now suppose that you're at some node $v$. If you have a next sibling, then you output the leftmost descendant of that sibling. If you don't have a next sibling, then you output the parent. If you don't have a parent, you're done.

$\endgroup$
  • $\begingroup$ This is similar to the solution that the data structures professor who proposed the problem used to solve it. The discrete math professor objected that "this has become a graph rather than a tree" if there are pointers back to the parents. $\endgroup$ – Nathan L Nov 8 '13 at 22:36
  • $\begingroup$ @NathanLiddle: That would depend on the tree definition used (which you did not give). In the "real world", Yuval's tree representation is reasonable even if graph theory would say the things he defines are not trees, of course. $\endgroup$ – Raphael Nov 9 '13 at 15:15
  • $\begingroup$ @Raphael Yes, and it meets the original professor's requirements, so it is an acceptable answer to me. $\endgroup$ – Nathan L Nov 10 '13 at 21:50
0
$\begingroup$

My solution was a bredth-first traversal using nested for-loops to brute force the tree. This isn't efficient by any means, and indeed a recursive data-structure like a tree is begging for a recursive traversal, but the question wasn't whether a tree could be traversed efficiently, is was whether it was even possible.

Pseudocode:
root = pointer root 
depth = integer 0
finished = bool false
//If we n-ary tree also track how many children have been found 
//on the node with the most children for the purposes of this psuedocode 
//we'll assume a binary tree and insert a magic number of 2 so that we 
//can use bitwise operators instead of integer division 
while(!finished)
    ++depth
    treePosition = pointer root
    finished = true;
    for i := 0..2**depth
        for j := 0..depth
            if (i & j) //bitwise operator explained below
                // if right child doesn't exist break the loop
                treePosition = treePosition.rightChild
            else
                // if left child doesn't exist break the loop
                treePosition = treePosition.leftChild
        if j has any children
            finished = false
            do anything else you want when visiting the node

For the first few levels it would look like this, as you can see, the bitwise operator in the pseudocode simply decides a left or right turn on a binary tree:

2**1       0               1
2**2   00      01      10      11
2**3 000 001 010 011 100 101 110 111

For n-ary, you would take i%(maxChildren**j)/j to determine which path to take between 0 and maxChildren.

At each node on n-ary you would also need to check to see if the number of the children is greater than maxChildren and update it appropriately.

$\endgroup$
  • $\begingroup$ If you wanted to use more than binary, you would need to replace the magic number 2 with a variable that would be incremented to match the max children that it saw, and instead of bitwise operators you would need to divide by that same variable raised to the power of the depth of the tree where you were. $\endgroup$ – Nathan L Nov 9 '13 at 16:35
  • $\begingroup$ If I understand correctly, this solution uses more than $O(1)$ additional space. If the tree is balanced, it uses $O(\lg n)$ bits (we could plausibly call this $O(1)$ words in a RAM integer model), but if the tree is unbalanced, it could use up to $O(n)$ additional bits, which is an unreasonable amount. Therefore, this probably shouldn't qualify, if the problem statement is posed carefully enough (e.g., what the professor probably had in mind was "using at most $O(1)$ additional space"). For instance, what do you do if depth exceeds the width of int? $\endgroup$ – D.W. Nov 10 '13 at 1:53
  • $\begingroup$ D.W., the professor who posed the problem did not put that constraint on the problem, and what bothered me so much about my discussion with the discrete math professor is that he NEVER acknowledged that it was even possible to traverse a tree without recursion, stack, or queue, whatever the cost. The only thing that my solution demonstrates is that it is possible do anything iteratively that can be done recursively, even if you remove options for stack, queue, etc. $\endgroup$ – Nathan L Nov 10 '13 at 2:29
  • $\begingroup$ It is one thing to say it is unsolvable without O(1) additional space, it is quite another to declare the problem unsolvable without recursion, stack, or queue. And actually, after seeing my code the discrete math professor still would not concede the point because he said "i" in the first for loop was taking the place of a queue. How's that for hard-headed? $\endgroup$ – Nathan L Nov 10 '13 at 2:33
  • 1
    $\begingroup$ @NathanLiddle, check again. Your integer i is depth bits wide. If depth is $\Theta(n)$ (which it could be, in unbalanced trees), then you need $\Theta(n)$ space to store the integer i, so the solution needs more than $O(1)$ additional space. $\endgroup$ – D.W. Nov 11 '13 at 1:41

Your Answer

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

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