# BST traversal without stack or recursion (?)

**SPOILER**: *this article assumes quite a lot of things about your knowledge of binary trees and data structure. I won't spend much time introducing concepts. Deal with it.*

Some time ago I had the pleasure to meet with Chris Lord, who introduced me to the concept of Binary Tree Traversal without using neither a stack/queue or recursion.

The list of requirements that such algorithm has to fulfil:

- Constant Space: no extra data structure to do the traversal
- Non-destructive: once finished, the tree needs to be exactly how it was before the visit

Sounded *crazy* initially, but than I looked into it more deeply and discovered, thanks to some pointers from Luca Colantonio, that there is an algorithm *in literature* that does just that: **Morris In-Order** Traversal.

Morris does just that - and a very good description of how it works can be found on Stack Overflow. I suggest you have a good read and come back: pointless of me to repeat it here.

...

You back? Great!

So, before "discovering" the Morris algorithm, I was trying to write a solution myself. My basic idea was to:

- Move downwards
- Manipulate pointers to the branch we are about to explore, to point backward so we have "a way back"
- Restore once done with that branch

At that stage, it had not occur to me to try to manipulate the entire tree structure like Morris does: I wanted to be very subtle, with the data structure resembling the original tree (though, with backward pointers).

The key issue I hit? **Going Backward**. Once I'm done visiting the branches of a node, I need to go back to the parent (to which I have a pointer too), and restore the structure.

**But HOW am I going to reconstruct the tree?** How do I know if the Branch I just visited was the *left* or the *right* branch of the parent I want to move back to?

## Downsize the problem

In a general Binary Tree, there is no guarantee of the order and distribution of nodes. It's just a tree where every node has 0, 1 or 2 child nodes. I didn't have any "rule" on which to **build a backward-restoring logic**.

But then I had an idea: what about BSTs (Binary Search Tree)? In those trees, there is a strong order relationship between a node and its childs.

This means that at any moment in time, once I'm done visiting a branch, I can reconstruct *where I'm coming from*, looking at the values of the parent and the child:

```
parent->value > child->value ? is_left_child : is_right_child
```

And, so I wrote the **De Marino BST Post-Order Traversal** algorithm:

```
void de_marino_bst_post_order_traversal(node *root) {
node *curr = root; //< current node
node *par = NULL; //< parent of current node
node *next = root; //< next node to traversal (but sometimes, just temp variable)
int dir = DOWN; //< direction in which we are moving
do {
if (dir == DOWN && curr->left != NULL) {
// Go down left
next = curr->left;
curr->left = par;
par = curr;
curr = next;
} else if (dir == DOWN && curr->right != NULL) {
// Go down right
next = curr->right;
curr->right = par;
par = curr;
curr = next;
} else {
printf("%d\n", curr != NULL ? curr->value : -1);
if (par->value > curr->value && par->right != NULL) {
// Go down right, coming from left
// NOTE: order gives us a hint about where we come from
dir = DOWN;
next = par->left; // hold the way back
par->left = curr;
curr = par->right;
par->right = next; // store the way back in the right child of par now
next = curr;
} else {
dir = UP;
if (par->value > curr->value) {
// Go up, coming from left
// NOTE: order gives us a hint about where we come from
next = par->left;
par->left = curr;
} else {
// Go up, coming from right
// NOTE: order gives us a hint about where we come from
next = par->right;
par->right = curr;
}
curr = par;
par = next;
}
}
} while(next != NULL && par != NULL);
printf("%d\n", curr != NULL ? curr->value : -1);
}
```

Now, I'm almost 100% sure that I'm not the first one to *stumble* into something like this, but for now I'm unable to find anything in literature - *cough* ... Google ... *cough* .

## An advantage over Morris

Yes, this algorithm requires the **strong condition of BST** while Morris works with any Binary Tree. That's a given. But this algorithm is also **faster**: it doesn't go deep into the tree to find the rightmost left child of a node, like Morris. From a quick look **the computation is linear - O(n)**: every node is visited only once. But maybe I'm overlooking something in Morris.

## Far from perfect

I'm also sure that this algorithm is **far from bug-less**: I have spent on it less than 24h between coding and thinking. So, please, to all the Computer Scientists people out there: let me know your thoughts and critics. This is a great way to spend some of that theory that we have in our heads.

I have added this code to my coding exercises repo on GitHub, if you want to try it out (check latest commits).

Now, as I expect, feel free to ignore my warnings and start your opinionated trashing - I'm pretty confident I'd deserve it. :)