Groovy Goodness: Preorder And Postorder Tree Traversal

The Node class in Groovy has the methods depthFirst and breadthFirst to return a collection of Node objects using either depth or breadth first traversal. Since Groovy 2.5.0 we can specify if we want to use preorder (the default) or postorder traversal. Also the methods now accept a Closure that will be invoked for each visited node. The Closure has the current Node as first argument, the second argument is the tree level of the current node.

In the following example we read some XML and then use depthFirst in several ways to visit the tree of nodes:

// We start with a XML node hierarchy.
def xml = '''
        <A>
          <B>
            <D/>
            <E/>
          </B>
          <C>
            <F/>
          </C>
        </A>
        '''
def root = new XmlParser().parseText(xml)

// Preorder traversal is default, but
// we can also specify it with the boolean
// argument of depthFirst method.
assert root.depthFirst(true)
           .collect { node -> node.name() } == ['A', 'B', 'D', 'E', 'C', 'F']
           
// Groovy 2.5.0 adds possibility to
// directly call closure for 
// each node visited where the first
// Closure argument is the node and
// the second argument the level.
def result = []
root.depthFirst { node, level -> result << "$level${node.name()}" }

assert result == ['1A', '2B', '3D', '3E', '2C', '3F']

// Postorder traversal can be specified
// by setting preorder argment to false.
// When used in combination with Closure
// argument we must using named argument
// preorder.
result = []
root.depthFirst(preorder: false) { node -> result << node.name() }

assert result == ['D', 'E', 'B', 'F', 'C', 'A']

In our second example we use the breadthFirst method. This means the nodes for visited per level in the tree:

// Let's create a Node hierarchy.
def builder = NodeBuilder.newInstance()
def root = builder.A {
    B {
        D()
        E()
    }
    C {
        F()
    }
}


// Preorder traversal is default, but
// we can also specify it with the boolean
// argument of breadthFirst method.
assert root.breadthFirst(true)
           .collect { node -> node.name() } == ['A', 'B', 'C', 'D', 'E', 'F']
           
// Groovy 2.5.0 adds possibility to
// directly call closure for 
// each node visited with node and level.
def result = []
root.breadthFirst { node, level -> result << "$level${node.name()}" }

assert result == ['1A', '2B', '2C', '3D', '3E', '3F']

// Postorder traversal is implemented
// as starting at the lowest level and 
// working our way up.
result = []
root.breadthFirst(preorder: false) { node -> result << node.name() }

assert result == ['D', 'E', 'F', 'B', 'C', 'A']

Written with Groovy 2.5.0.

Search

June 25, 2018

Groovy Goodness: Preorder And Postorder Tree Traversal