Find Minimum and Maximum in a Binary Tree in Kotlin | BST

by

To find the minimum and maximum values in a binary search tree, we can simply traverse the tree as follows:

  • To find the minimum value, start at the root node and keep going left until we reach a leaf node.
  • To find the maximum value, start at the root node and keep going right until we reach a leaf node.

Example :

        5
      /   \
     3     7
    / \   / \
   2   4 6   8

Minimum value: 2 And Maximum value: 8

Kotlin
fun findMin(root: TreeNode?): Int {
    var node = root
    while (node?.left != null) {
        node = node.left
    }
    return node?.`val` ?: throw IllegalArgumentException("Tree is empty")
}

The findMin function starts at the root node and keeps traversing the left child nodes until it reaches a leaf node. It returns the value of the last node visited, which will be the minimum value in the tree.

Kotlin
fun findMax(root: TreeNode?): Int {
    var node = root
    while (node?.right != null) {
        node = node.right
    }
    return node?.`val` ?: throw IllegalArgumentException("Tree is empty")
}

The findMax function is similar, except it starts at the root node and keeps traversing the right child nodes until it reaches a leaf node. It also returns the value of the last node visited, which will be the maximum value in the tree.

Kotlin
class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}
fun findMin(root: TreeNode?): Int {
    var node = root
    while (node?.left != null) {
        node = node.left
    }
    return node?.`val` ?: throw IllegalArgumentException("Tree is empty")
}
fun findMax(root: TreeNode?): Int {
    var node = root
    while (node?.right != null) {
        node = node.right
    }
    return node?.`val` ?: throw IllegalArgumentException("Tree is empty")
}
fun main() {
    // Create a binary search tree
    val root = TreeNode(5)
    root.left = TreeNode(3)
    root.left!!.left = TreeNode(2)
    root.left!!.right = TreeNode(4)
    root.right = TreeNode(7)
    root.right!!.left = TreeNode(6)
    root.right!!.right = TreeNode(8)

    // Find the minimum and maximum values
    val minVal = findMin(root)
    val maxVal = findMax(root)

    // Print the results
    println("Minimum value: $minVal")
    println("Maximum value: $maxVal")
}

main function creates a binary search tree with the same structure as the one used in the previous example, and then calls the findMin and findMax functions to find its minimum and maximum values. Finally, it prints the results to the console.

Minimum value: 2

Maximum value: 8

Leave a Comment