# What is a binary tree and how to invert it using 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
}``````