Kotlin Recursive function: Find maximum depth of binary tree

Kotlin Function: Exercise-11 with Solution

A binary tree is a rooted tree that is also an ordered tree (a.k.a. plane tree) in which every node has at most two children. A rooted tree naturally imparts a notion of levels (distance from the root), thus for every node a notion of children may be defined as the nodes connected to it a level below.

Write a Kotlin recursive function to find the maximum depth of a binary tree.

Sample Solution:

Kotlin Code:

data class TreeNode(val value: Int, val left: TreeNode?, val right: TreeNode?)

fun maxDepth(root: TreeNode?): Int {
    if (root == null) {
        return 0
    }
    
    val leftDepth = maxDepth(root.left)
    val rightDepth = maxDepth(root.right)
    
    return 1 + maxOf(leftDepth, rightDepth)
}

fun main() {
    val tree = TreeNode(
        1,
        TreeNode(
            2,
            TreeNode(4, null, null),
            TreeNode(5, null, null)
        ),
        TreeNode(
            3,
            TreeNode(6, null, null),
            null
        )
    )

    val depth = maxDepth(tree)
    println("Maximum depth of the binary tree: $depth")
}

Sample Output:

Maximum depth of the binary tree: 3

Explanation:

In the above exercise -

• First, we define a data class 'TreeNode' that represents a node in a binary tree. Each 'TreeNode' has a value, a left child node, and a right child node.
• The "maxDepth()" function is the recursive function that finds the maximum depth of the binary tree. It takes a root node as its parameter. The function follows these steps:
• If the root is null, it means we have reached the leaf node or an empty tree. In this case, we return 0.
• Otherwise, we make recursive calls to 'maxDepth' for the left and right subtrees, obtaining their respective depths (leftDepth and rightDepth).
• The function returns 1 plus the maximum of leftDepth and rightDepth, representing the depth of the current node and its deepest subtree.
• In the "main()" function, we create a binary tree by constructing TreeNode instances and linking them together. We then call the 'maxDepth' function with the root node of the binary tree and store the result in the depth variable. Finally, we print the maximum depth of the binary tree.

Kotlin Editor:

Previous: Sum of even Fibonacci numbers.
Next: Binary tree as a binary search tree.