Height of a Binary Tree in Kotlin

In computer science, a binary tree is a tree data structure where each node can have at most two children, referred to as the left child and the right child. The height of a binary tree is the length of the longest path from the root node to a leaf node.

In other words, the height of a binary tree is the maximum number of edges in any path from the root node to a leaf node. A leaf node is a node with no children.

For example, in a binary tree with a single node, the height is 0. In a binary tree with two nodes where one is the parent of the other, the height is 1. In a binary tree where the root has two children and each of those children has two children, the height is 2.

The height of a binary tree can be important for understanding the efficiency of certain algorithms that use binary trees, such as binary search trees. The height of a balanced binary tree, where the left and right subtrees have similar heights, is typically O(log n), where n is the number of nodes in the tree. However, the height of an unbalanced binary tree can be as high as O(n), where n is the number of nodes in the tree, which can significantly affect the performance of algorithms that use the tree.

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

fun height(root: Node?): Int {
    return if (root == null) {
        -1
    } else {
        1 + maxOf(height(root.left), height(root.right))
    }
}

fun main() {
    // create a binary tree
    val root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left?.left = Node(4)
    root.left?.right = Node(5)
    root.right?.left = Node(6)
    root.right?.right = Node(7)

    // calculate the height of the binary tree
    val treeHeight = height(root)

    // print the height of the binary tree
    println("Height of the binary tree is: $treeHeight")
}

The height function takes a binary tree root as input and returns its height. If the root is null, the function returns -1. Otherwise, it recursively calculates the height of the left and right subtrees and returns the maximum of the two heights plus 1.

In the main function, a binary tree is created with seven nodes, and the height function is called to calculate its height. The result is then printed to the console.

This program outputs: 2

since the binary tree has a height of 2.