2018-3-18

What is a binary tree and how to invert it using Kotlin

Explanation of what a binary tree is, what it means to invert a binary tree and how to do it in Kotlin.

A binary tree is a data structure in which each node has at most two children. The children are referred to as the left child and the right child.

                    1
                  /   \    
   (Left Child)  2     3  (Right Child)
                / \
 (Left Child)  4   5  (Right Child)             

To invert, sometimes also called to mirror or reverse, a binary tree is to interchange all left and right nodes.

   (Original)     (Inverted)

       1              1
     /   \          /   \      
    2     3        3     2
   / \   / \      / \   / \
  4   5 6   7    7   6 5   4
 /                          \
8                            8

Given that a node has this shape.

class TreeNode(var value: Int = 0) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

Inverting can be done by recursivly walking through the tree and on every level change left for right and right for left.

fun invert(root: TreeNode?): TreeNode? {
    // Check if we have a node.
    if (root == null) {
        return null
    }

    // Invert the sub structures and save the result
    // to temporary variables.
    val right: TreeNode? = invert(root.right)
    val left: TreeNode? = invert(root.left)

    // Switch places.
    root.left = right
    root.right = left

    // Return the root.
    return root
}
Jan Järfalk — User experienced esthete, technician, geek and web worker. Aspiring artist and recreational mathematician. I indulge and travel plenty. Constraints are good.