## Iterative Binary Tree Traversal

Traversal of binary trees has a simple recursive solution. This blog describes an iterative C++ function derived from a defunctionalised Ocaml solution to the problem.

Introduction
Consider the following code to compute the height of a binary tree.

```struct Tree{
Tree* left;
Tree* right;
int val;
};
struct Recursive {
static int height(Tree* root){
if(root){
auto lh = height(root->left);
auto rh = height(root->right);
return 1 + std::max(lh,rh);
}else{
return 0;
}
}
};
```

This code builds up the stack which is a scarce resource compared to the heap. An iterative solution is shown below:

```struct Iterative {
static int height(Tree *root){
enum class item_type { tree, height};
struct item {
item_type type;
union {
Tree* root;
unsigned height;
};
item(Tree* r):type(item_type::tree)
{root=r;}
item(unsigned h):type(item_type::height)
{height=h;}

};
bool go_on=true;
unsigned depth = 0;
std::stack<item> items;
while (go_on) {

if (root) {
item it(root->right);
items.push(it);
root = root->left;
} else {
go_on=false;
depth=0;
while (!items.empty()&& !go_on) {
item cur = items.top();
items.pop();
switch (cur.type) {
case item_type::tree: {
item next(depth);
items.push(next);
root = cur.root;
go_on = true;
}
break;
case item_type::height: {
depth = 1 + std::max(depth, cur.height);
//depth = 1 + depth + cur.height;
}
break;
}
}
}
}
return depth;
}
};
```

The rest of the blog documents my journey from an OCaml solution to a C++ version. I started with attempting to have a tail recursive solution in OCaml. This lead me to CPS (continuation passing style). The CPS version was then defunctionalized to two mutually recursive functions that was then translated to C++ and then inlined to the iterative method shown above.

Continuation Passing Style
The recursive OCaml solution is shown below:

``````type 'a tree = Leaf of a' | Node of a' * a' tree * a' tree;;
let depth = function
| Leaf x -> 0
| Node(_, left,right) ->
let l = depth left in
let r = depth right in
1 + (max l r)
``````

The CPS modification as Gasche suggests is straightforward as shown below:

```let depth tree =
let rec depth tree k = match tree with
| Leaf x -> k 0
| Node(_,left,right) ->
depth left (fun dleft ->
depth right (fun dright ->
k (1 + (max dleft dright))))
in depth tree (fun d -> d)
```

Gasche then defunctionalizes the above code as follows:

```type ('a, 'b) cont =
| Kleft of 'a tree * ('a, 'b) cont (* right and k *)
| Kright of 'b * ('a, 'b) cont     (* dleft and k *)
| Kid
```

```let depth tree =
let rec depth tree k = match tree with
| Leaf x -> eval k 0
| Node(_,left,right) ->
depth left (Kleft(right, k))
and eval k d = match k with
| Kleft(right, k) ->
depth right (Kright(d, k))
| Kright(dleft, k) ->
eval k (1 + max d dleft)
| Kid -> d
in depth tree Kid
;;
```

As Gasche points out `cont` is essentially a linked list and hence the above code can be transformed as shown below:

```type ('a, 'b) next_item =
| Kleft of 'a tree
| Kright of 'b

type ('a, 'b) cont = ('a, 'b) next_item list

let depth tree =
let rec depth tree k = match tree with
| Leaf x -> eval k 0
| Node(_,left,right) ->
depth left (Kleft(right) :: k)
and eval k d = match k with
| Kleft(right) :: k ->
depth right (Kright(d) :: k)
| Kright(dleft) :: k ->
eval k (1 + max d dleft)
| [] -> d
in depth tree []
;;
```

However the list is accessed like a stack with adding and removing only from the top. From here the C++ solution quickly follows.

```type ('a, 'b) next_item =
| Kleft of 'a tree
| Kright of 'b
```

can be translated to C++ as:

`enum class item_type { tree, height}; struct item {   item_type type;   union { Tree* root; unsigned height; }; }; `

The constructors for `item` are just syntactic sugar. The rest of the OCaml code can be translated as:

```struct Iterative_1 {

static int height_aux(Tree *root, stack<tem>& items){
if(root)
{
item it(root->right);
items.push(it);
return height_aux(root->left,items);
} else {
return eval(items, 0);
}

}
static int eval(stack<item>& items, unsigned depth){
if(items.empty()){
return depth;
}else{

item cur = items.top();
items.pop();
switch (cur.type)
{
case item_type::tree:
{
item next(depth);
items.push(next);
return height_aux(cur.root, items);
}
case item_type::height:
{
return eval(items,  1 + std::max(depth, cur.height));
}
}
}

}
static unsigned height(Tree* root){
std::stack<item>items;
return height_aux(root,items);
}
```

Since the recursive calls are all tail recursive we could replace each recursive call with `goto`. But `goto` in code is bad for your health and that of the code. Hence we replace it with loops as shown below.

```
static int height_aux(Tree *root, std::stack<item>& items){
while (root)
{
item it(root->right);
items.push(it);
root= root->left;
}
return eval(items, 0);

}
static int eval(std::stack<item>&  items, unsigned depth){
while (!items.empty()){

item cur = items.top();
items.pop();
switch (cur.type)
{
case item_type::tree:
{
item next(depth);
items.push(next);
return height_aux(cur.root, items);
}
case item_type::height:
{
depth =  1 + std::max(depth, cur.height);
}
}
}

return depth;
}

```

Now if we inline `eval` inside `height_aux` a direct translation we would still require a `goto`.
The variable `go_on` as shown in the introduction is a work-around for `goto`

Modifying the the iterative to compute additional properties such the number of nodes is done by replacing

```depth = 1 + std::max(depth, cur.height);
```

with

```depth = 1 + depth + cur.height;
```

Computing values such as the maximum value of all the nodes, or its mean or variance should now be trivial.

Personal Note
I would not have come up this solution but for the OCaml code. Thus learning a functional programming language is of great use even for writing code in languages like C++/C#/Java. 