Algorithms - Binary tree traversals in kotlin

Traversals :

"Tree traversal refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited." -— Wikipedia

There are 2 options:

• DFS : Depth-First Search _“is an algorithm for traversing or searching tree data structure. One starts at the root and explores as far as possible along each branch before backtracking.” -— Wikipedia
• BFS : Breadth-First Search “is an algorithm for traversing or searching tree data structure. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors." -— Wikipedia

DFS - Depth-First Search

DFS algorithms start from the root and goes deep as possible until they find a leaf before backtracking and exploring another path. The main 3 DFS types are:

• Pre-Order: (NLR) process node data, left child and finally right child
• In-Order: (LNR) process left child, node data and finally right child
• Post-Order: (LRN) process left child, right child and finally node data

Kotlin Examples:

Usually the DFS algorithms are ease to implement with recursion.

Binary tree

data class BinaryTreeNode(
        val data:Int,
        val left:BinaryTreeNode? = null,
        val right:BinaryTreeNode? = null
)

Preorder traversal

fun preOrderTraversal(node: BinaryTreeNode?, 
                      operation: (BinaryTreeNode) -> Unit){
    if (node == null) return;
    // Visit node
    operation.invoke(node)
    // Traverse left
    preOrderTraversal(node.left,operation);
    // Traverse right
    preOrderTraversal(node.right,operation);
}

InOrder traversal

fun inOrderTraversal(node: BinaryTreeNode?, 
                     operation: (BinaryTreeNode) -> Unit){
    if (node == null) return;
    // Traverse left
    inOrderTraversal(node.left,operation);
    // Visit node
    operation.invoke(node)
    // Traverse right
    inOrderTraversal(node.right,operation);
}

PostOrder traversal

fun postOrderTraversal(node: BinaryTreeNode?, 
                       operation: (BinaryTreeNode) -> Unit){
    if (node == null) return;
    // Traverse left
    postOrderTraversal(node.left,operation)
    // Traverse right
    postOrderTraversal(node.right,operation)
    // Visit node
    operation.invoke(node)
}

BFS - Breadth-First Search

For BFS algorithm we are going to use a queue:

• Push root node to the queue
• While queue is not empty:
  • Poll element from queue and process data
  • If left child exist, add to the queue
  • If right child exist, add to the queue

   fun bfs(node: BinaryTreeNode, operation: (BinaryTreeNode) -> Unit){

        val queue = LinkedList<BinaryTreeNode>() as Queue<BinaryTreeNode>
        queue.offer(node)
        var current : BinaryTreeNode

        while(!queue.isEmpty()){
            current = queue.poll()
            operation.invoke(current)

            if (current.left != null){
                queue.offer(current.left)
            }
            if (current.right != null){
                queue.offer(current.right)
            }
        }
    }

You can find the complete code of this example in this GitHub repository