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.