Zeuthen: Writing a C library, part 1
Posted Jun 30, 2011 6:07 UTC (Thu) by dark
In reply to: Zeuthen: Writing a C library, part 1
Parent article: Zeuthen: Writing a C library, part 1
You can do it in O(n) by abusing the child pointers of nodes that you've visited but not yet destroyed. For example if you always descend to the left node first, then you can put the current node on a linked list that's threaded through the left pointers. When you hit the bottom of the tree, you take a node out of the linked list, destroy it, and proceed to its right child.
This way you visit each node a constant number of times (once to put it on the list, once to take it off) and you only need two temporary pointers: one for the start of the list and one for the child to visit next. You can optimize a bit for leaf nodes but that doesn't impact the time complexity.
Managing the linked list is easy because you're just using it as a stack.
to post comments)