Half a decade ago I was sitting in a data structures class where the professor o
ID: 657029 • Letter: H
Question
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.
Explanation / Answer
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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.