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:

struct Node {
	Node* lchild;
	Node* rchild;
	Node* parent;
	union {
		size_t pos;
		uint8_t ins;
	};
};

(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:

struct Node emptyNode = { 0 };
struct Node* nodehead = new Node(emptyNode);

Use the copy construction ;)

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

int curLevel = 1;
int c = 1;

while (true) {
	if (curLevel < TREE_DEGREE && !curnode->lchild) {
		curLevel++;
		curnode->lchild = new Node(emptyNode);
		curnode->lchild->parent = curnode;
		curnode = curnode->lchild;
		curnode->pos = c++;
	}
	else {
		if (!curnode->parent->rchild) {
			curnode->parent->rchild = new Node(emptyNode);
			curnode->parent->rchild->parent = curnode->parent;
			curnode = curnode->parent->rchild;
			curnode->pos = c++;
		}
		else {
			curLevel--;
			curnode = curnode->parent;
		}
	}
	if (curLevel == 1) {
		break;
	}
}

(A little long, but still easy enough)

Fourth, delete selected a leaf node:

int selected = rand() % (remainingLeafNode - 1);
int curLayer = 1;
Node* curnode = nodehead;
bool deleteFail = 0;
while (true) {
	if (curLayer < TREE_DEGREE - 1) {
		if (selected >= pow(2, TREE_DEGREE - curLayer - 1)) {
			curnode = curnode->rchild;
			selected -= pow(2, TREE_DEGREE - curLayer - 1);
		}
		else {
			curnode = curnode->lchild;
		}
	}
	else {
		if (selected == 0) {
			if (!curnode->lchild)
				deleteFail = true;
			else
				curnode->lchild = NULL;
		}
		else {
			if (!curnode->rchild)
				deleteFail = true;
			else
				curnode->rchild = NULL;
		}
		break;
	}
	curLayer++;
}

(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:

while (true) {
	while (curnode->lchild) {
		curnode = curnode->lchild;
	}

	if (!curnode->rchild) // leaf node here 
		visit(curnode);
	else { // no left child, but have a right child
		curnode = curnode->rchild;
		continue;
	}
	
	// a leaf node
	if (curnode->parent->lchild == curnode) { // a leaf left node finished, go to its sibiling
		if (curnode->parent->rchild) { // has a right sibiling, redoing the process above
			curnode = curnode->parent->rchild;
			continue;
		}
	}
	else {
		// a leaf right node
		while (curnode->parent && curnode == curnode->parent->rchild) {// way up until it's a left node or root node
			curnode = curnode->parent;
			visit(curnode);
		}
		if (curnode == nodehead) {
			break;
		}
		if (curnode->parent->rchild)
			curnode = curnode->parent->rchild;
	}
}

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 :)

while (true) {
	while (curnode->lchild) {
		curnode = curnode->lchild;
	}
	if (curnode->rchild) { // no left child, but have a right child
		curnode = curnode->rchild;
		continue;
	}

	bool doingRightNodeBacktrack = false;
	bool hasRightNodeBacktrack = false;
	while (true){
		if (hasRightNodeBacktrack && !doingRightNodeBacktrack) {
			break;
		}
		if (doingRightNodeBacktrack || !curnode->rchild) { // short-circuit if doingRightNodeBacktrack is true
			// leaf node here 
			visit(curnode);
		}

		// a leaf node
		if (curnode->parent && curnode->parent->lchild == curnode) { // a leaf left node finished, go to its sibiling
			if (curnode->parent->rchild) { // has a right sibiling, redoing the process above
				curnode = curnode->parent->rchild;
				break;// break into the outer while loop
			}
		}
		else {
			// a leaf right node
			if (curnode->parent && curnode == curnode->parent->rchild) {// way up until it's a left node or root node
				curnode = curnode->parent;
				doingRightNodeBacktrack = true;
				hasRightNodeBacktrack = true;
			}
			else {
				doingRightNodeBacktrack = false;
			}
		}
	}
	if (curnode == nodehead) {
		break;
	}
	if (hasRightNodeBacktrack) {
		if (curnode->parent->rchild)
			curnode = curnode->parent->rchild;
	}
}

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