Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Groovy Goodness: Preorder and Postorder Tree Traversal [Snippet]

DZone's Guide to

Groovy Goodness: Preorder and Postorder Tree Traversal [Snippet]

Check out this new Groovy post and learn how to use preorder and postorder for a tree traversal in Groovy 2.5.0.

· Java Zone ·
Free Resource

Download Microservices for Java Developers: A hands-on introduction to frameworks and containers. Brought to you in partnership with Red Hat.

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 the 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 that the nodes are 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.

Download Building Reactive Microservices in Java: Asynchronous and Event-Based Application Design. Brought to you in partnership with Red Hat

Topics:
java ,groovy ,groovy 2.5.0 ,preorder ,postorder

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}