CODEWITHSUNDEEP
algorithmtreefunctional-programmingocaml
qiubit
qiubit

Reputation: 4816

Magic code for level binary tree traversal - what is going on?

We have a definition of binary tree:

type 'a tree =
  | Node of 'a tree * 'a * 'a tree
  | Null;;

And also a helpful function for traversing the tree"

let rec fold_tree f a t =
  match t with
  | Null -> a
  | Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;

And here is a "magic" function which, when given a binary tree, returns a list in which we have lists of elements on particular levels, for example, when given a tree:

tree
(source: ernet.in)

the function returns [[1];[2;3];[4;5;6;7];[8;9]].

let levels tree =
  let aux x fl fp = 
    fun l ->
    match l with
    | [] -> [x] :: (fl (fp []))
    | h :: t -> (x :: h) :: (fl (fp t))
  in fold_tree aux (fun x -> x) tree [];;

And apparently it works, but I can't wrap my mind around it. Could anyone explain in simple terms what is going on? Why does this function work?

Upvotes: 3

Views: 379

Answers (1)

n. m. could be an AI
n. m. could be an AI

Reputation: 119857

How do you combine two layer lists of two subtrees and get a layer list of a bugger tree? Suppose you have this tree

   a
  / \
 x   y

where x and y are arbitrary trees, and they have their layer lists as [[x00,x01,...],[x10,x11,...],...] and [[y00,y01,...],[y10,y11,...],...] respectively.

The layer list of the new tree will be [[a],[x00,x01,...]++[y00,y01,...],[x10,x11,...]++[y10,y11,...],...]. How does this function build it?

Let's look at this definition

let rec fold_tree f a t = ...

and see what kind of arguments we are passing to fold_tree in our definition of levels.

... in fold_tree aux (fun x -> x) tree []

So the first argument, aux, is some kind of long and complicated function. We will return to it later.

The second argument is also a function — the identity function. This means that fold_tree will also return a function, because fold_tree always returns the same type of value as its second argument. We will argue that the function fold_tree applied to this set of arguments takes a list of layers, and adds layers of a given tree to it.

The third argument is our tree.

Wait, what's the fourth argument? fold_tree is only supposed to get tree? Yes, but since it returns a function (see above), that function gets applied to that fourth argument, the empty list.

So let's return to aux. This aux function accepts three arguments. One is the element of the tree, and two others are the results of the folds of the subtrees, that is, whatever fold_tree returns. In our case, these two things are functions again.

So aux gets a tree element and two functions, and returns yet another function. Which function is that? It takes a list of layers, and adds layers of a given tree to it. How it does that? It prepends the root of the tree to the first element (which is the top layer) of the list, and then adds the layers of the right subtree to the tail of the list (which is all the layers below the top) by calling the right function on it, and then adds the layers of the left subtree to the result by calling the left function on it. Or, if the incoming list is empty, it just the layers list afresh by applying the above step to the empty list.

Upvotes: 2

Related Questions