Binary Tree Traversals

Get ready to embark on an exciting journey through the woods — the binary woods, that is. A Binary Tree is a fundamental data structure in which each node has at most two children, referred to as the left child and the right child. Traversing such a structure involves visiting each node in a specific order. With its strong type system and modern features, Kotlin provides a safe and efficient way to navigate these hierarchical structures.

Before diving deeper into the traversals, let's define a structure for a binary tree node in Kotlin. Each node in a binary tree will have a value, a reference to its left child, and a reference to its right child.

Here’s how you can define a TreeNode class in Kotlin using a primary constructor:

class TreeNode(
    var value: Int,
    var left: TreeNode? = null,
    var right: TreeNode? = null
)

In this TreeNode class:

• value represents the data stored in the node.
• left and right are properties that point to the node's children.
• We use the ? symbol to declare these properties as nullable (TreeNode?), allowing them to be null if a child does not exist.
• By providing default values of null, we can easily create nodes without children.

We have three primary ways to traverse a binary tree: Inorder (Left, Root, Right), Preorder (Root, Left, Right), and Postorder (Left, Right, Root).

One common method is the recursive Inorder traversal. If a node exists, we first recursively traverse the left subtree, then visit the current node's value, and finally, recursively traverse the right subtree.

In Kotlin, we can implement this efficiently by using a MutableList to collect the values as we visit them:

fun inorderTraversal(root: TreeNode?): List<Int> {
    val result = mutableListOf<Int>()

    fun traverse(node: TreeNode?) {
        // Return early if the node is null
        if (node == null) return

        traverse(node.left)       // Traverse Left
        result.add(node.value)    // Visit Root
        traverse(node.right)      // Traverse Right
    }

    traverse(root)
    return result
}

fun main() {
    // Constructing a tree: 1 -> Right: 2 (Left: 3)
    val root = TreeNode(1, null, TreeNode(2, TreeNode(3)))
    
    // Output the result of the traversal
    println(inorderTraversal(root))  // Output: [1, 3, 2]
}

This approach uses a nested helper function (traverse) to keep the list modification encapsulated while providing a clean List<Int> as the final result.

Understanding binary tree traversals will not only strengthen your problem-solving skills but also provide essential knowledge for many advanced topics, such as tree balancing or hierarchical data processing. So, get ready for the practice exercises! Remember, our goal here is not just rote learning of algorithms but rather gaining a deeper understanding of how complex problems can be solved with elegant and safe solutions.