Entry tags:

d language, programming

Tree visits in D
On the RosettaCode site there's this Programming Task:
http://rosettacode.org/wiki/Tree_traversal

Problem: Implement a binary tree where each node carries an integer, and implement preoder, inorder, postorder and level-order traversal. Use those traversals to output the following tree:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

The correct output should look like this:

preorder:    1 2 4 7 5 3 6 8 9
inorder:     7 4 2 5 1 8 6 9 3
postorder:   7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9

The following is my D implementation. I have used the D Version 2 language (to compile the code I am using DMD v2.032, with the Phobos std lib, but it uses only the printing of Phobos, so adapting the code to Tango is easy), but a very similar version can be adapted for D V1.

Disclaimer: The following isn't an example of common (or good) D code. It's very generic and it's a bit tricky. In practice you usually write simpler code, because you don't need such genericity, and to keep the code simpler to write and understand. Simpler code is also simpler to debug. You may need to write code so much generic only in library-like routines, that are usually limited in number and size. So there are surely ways to write simpler/shorter D code, but here I show this version because it can be useful to explain some features of the D language, and because it's more fun.

Output:
  preOrder: 1 2 4 7 5 3 6 8 9
   inOrder: 7 4 2 5 1 8 6 9 3
 postOrder: 7 4 5 2 8 9 6 3 1
levelorder: 1 2 3 4 5 6 7 8 9

A possible design for Java is to create a Node class (using generics to allow for different types of data) that has preOrder, InOrder, etc, methods. This simple design can be used in D too. But it conflates data structure and algorithms, so you can't use the same algorithms (the tree visits) for other kinds of nodes.

So if your language is flexible enough (like C++, D, Haskell, or Python) it's better to follow the strategy used in the C++ STL, and implement generic algorithms, that work with more kinds of binary tree nodes and allow for a more flexible management of the node being visited.

Another design that can be natural in modern versions of Python is to create iterators, that yield the current node. This is very handy, and such strategy can be used in D too (with opApply or with the second iteration protocol of D2) but I have not used it in my D code. In Python (and in some other languages, in D too if you use opApply) this strategy leads to O(n^2) tree visits. (There is a Python PEP that if well implemented may solve this problem).

Th flexibility of D language has allowed me to merge the three backtracking visits (pre, in and post - order) in a single templated function with zero overehead.

In the code I have used a class to represent the node to keep code a little simpler, but a struct too can be used with very small changes. Such structs are smaller 8 bytes less on a 32 bit system) and it's simpler to allocate them with a memory pool that can halve the time needed to create and allocate the tree.

I have added a helper node() templated function, it just allocates a new node and returns it. In D something similar can also be done with a static opCall inside Node, but here it's also templated, and templatd methods can't replace opCall of object (I may be wrong on this, but I don't think so). If you have a different Node class/struct you need a different helper function, or you have to use opCall (if the Node isn't generic) or you have to build the tree in a simpler way.

Node!T is the new compact syntax introduced in D2 to instantiate a template when you have a single argument. The standard older syntax is Node!(T), that equals to C++ Node.

show() is a little function that's used as default visitor of the node. It's templated, so you have to instantiate it before taking its address to use it as function pointer.

backtrackingOrder() merges the three tree visits, its code is a little tricky.

The enum Visit is used to represent one of the three possible visits. To specify it you can first partial specify backtrackingOrder() according to visit type known a compile-time, and then you can fully specify it automatically with the given root node and an optional callable.

The node can be any type that has a left, right and node attributes.

visitor can be any callable, a delegate, function pointer, or callable object. If visitor is unspecified you can omit it, and it uses show() instantiated on the type of the data.

The static ifs are done at compile time, and they don't create a scope, so truevisitor (its type is found automatically) is then visible under the static if. The is() syntax is used to test if types are the same (a better simpler design for the D language is just to allow == between them).

In library code you may add few more static asserts inside backtrackingOrder() to test that visitor is a callable, with a line of code like:
static assert(IsCallable!(typeof(truevisitor)), "...");