We are apologize for the inconvenience but you need to download
more modern browser in order to be able to browse our page

Download Safari
Download Safari
Download Chrome
Download Chrome
Download Firefox
Download Firefox
Download IE 10+
Download IE 10+

How to traverse through a binary tree with parent node pointer (without stack, without recursion)

Recently I have some research coding works, and I’ve met a big problem.

I’m patching a compiler, and to make the change as little as possible, I decided to write the whole patch in a function.

I thought it would be easy for me to achieve this, but I found it’s FAR MORE harder than I ever thought.

I’ve got to create a custom AST, so I can’t use the original implementation of tree, but to write a custom one.

So I have to write a tree implementation.


First of all, the definition of struct, quite easy:

(As we needed to do the iteration without function, we cannot use the recursive way, and I doesn’t wanted the tree to be changed, so I choose to include a parent node pointer.)

Second, how to create a empty node elegantly:

Use the copy construction ;)

Third, create a full binary tree with specified degree:(in a iterative way)

(A little long, but still easy enough)


Fourth, delete selected a leaf node:

(Every node is virtually mapped into a full binary tree which its leaf nodes are numbered from left to right)


Finally, we have to traverse through the tree: (Here I’ll only show you the last-root order traversing method)

You may thought I’ll show you with this one:


But that one has a fatal shortage, the visit code is called in two location, that means I would have to use a function, or to copy the code twice times.

OFC, neither of them satisfied me. Using a function is against my prerequsition, and copy code twice is ugly and not robust

So Instead, I changed the code structure and moved the while loop, introducing two flags, and finally we can have only one visit function here :)

That’s all~ Have a nice day~ :)