BST traversal without stack or recursion (?)
SPOILER: this article assumes quite a lot of things about your knowledge of binary trees and data structure. I won’t spend much time introducing concepts. Deal with it. Some time ago I had the pleasure to meet with Chris Lord, who introduced me to the concept of Binary Tree Traversal without using neither a stack/queue or recursion. The list of requirements that such algorithm has to fulfil: Constant Space: no extra data structure to do the traversal Non-destructive: once finished, the tree needs to be exactly how it was before the visit Sounded crazy initially, but than I looked into it more deeply and discovered, thanks to some pointers from Luca Colantonio, that there is an algorithm in literature that does just that: Morris In-Order Traversal. ...