Tree Traversals in Kotlin
Below are the classic binary tree recursive traversal methods embedded into our BinaryNode class. We use a companion object to minimize our space complexity, which is comparable to static methods in Java. You may wonder why we allow for a nullable BinaryNode to be passed into each of these methods. I settled at this option for the sake of clarity. Because the left and right nodes are mutable objects, we would need to create immutable references to them before passing them to the recursive calls. You could say our base case is an empty leaf node.
The wonderful part about Kotlin is that we can define our action as a lambda expression. Below you will see an action defined as a parameter, which uses the value of the node being passed in as the first parameter. Our action here returns Unit, which is comparable to returning void in Java. Let’s look at how we can use this lambda expression.
Forgive me for my crude test tree!
As you can see we can pass the root node to our traversal functions and define the action we can take when processing the value of the node as we pass through it. In our last call, just by changing our lambda expression, we define a Postorder search.
What about N-ary trees?
Below, similarly, is our Node with a list of children. We implement DepthFirst and BreadthFirst with stack and queue respectively. Our action is defined just as above.
Here we have a similarly awful test tree. We call the traversals the same way as we do with BinaryNode. This time getting extra fancy using when in our search variation.
Thank you for taking the time to reach this point. I’m always open to constructive criticism or suggestions on expanding the article. I created the above using IntelliJ Community Edition and you can download the project at the following link.
