Re:Tree traversal without recursion: the tree as a state mac...
by stuxnet79 on Tuesday September 03, 2019 @08:01AM
(#20865689)
Morris traversal of a binary tree is fairly straightforward once you clue into the fact that the child nodes left and right pointers are being used to reference the predecessor node and successor node respectively. That's it. Simple idea with big implications. I'll have a look at XOR Linked Lists. I've heard of them before but the implementation always looked awkward enough for it to not really be worth it imo.
[ Parent
| on HN ]
Re:Tree traversal without recursion: the tree as a state mac...
by kd5bjo on Tuesday September 03, 2019 @10:32AM
(#20866821)
The downside of an XOR-linked list is that a single pointer to a list node isn’t enough information to traverse the list. Instead, you need to know the addresses of two adjacent nodes. They also don’t have an innate directionality to them; swapping your two local pointers will have you following the list in the opposite direction.