Kotlin Recursive function: Find maximum depth of binary tree

Last update on February 04 2025 08:26:41 (UTC/GMT +8 hours)

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.

Pre-Knowledge (Before You Start!)

Before solving this exercise, you should be familiar with the following concepts:

Binary Tree: A tree structure in which each node has at most two children, typically referred to as the left and right child.
TreeNode Data Structure: A data class or object that represents a node in a binary tree, holding a value and references to left and right child nodes.
Recursion: A function calling itself to solve smaller parts of a problem incrementally. In this case, recursion will be used to traverse the tree.
Max Depth of a Binary Tree: The longest path from the root node to any leaf node in the tree. This is measured in terms of the number of nodes along the path.
Base Case in Recursion: In recursion, the base case is when the tree (or subtree) is empty (null), at which point the recursion should return 0.

Hints (Try Before Looking at the Solution!)

Here are some hints to help you solve the problem:

Hint 1: Use recursion to calculate the maximum depth of the left and right subtrees of each node.
Hint 2: At each node, calculate the depth by finding the maximum depth between its left and right subtrees and add 1 to account for the current node.
Hint 3: If the node is null (i.e., no child or leaf node), return 0 to indicate no further depth in that direction.
Hint 4: The recursion will stop when a leaf node is reached, returning the depth back up the 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.