Can a tree be traversed without recursion, stack, or queue, and just a handful of pointers?
A lot of research in this area has been done, motivated by method of &quot;cheaply&quot; 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 &quot;rotates&quot; 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