4 ms·
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
by stuxnet79 7y ago
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.
- kd5bjo 7y agoThe 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.