To Check if Binary Tree is Balanced in Kotlin

by

To check if a binary tree is balanced or not, we can use a recursive approach.

A binary tree is considered balanced if the difference between the height of its left and right subtrees is no more than one, and both the left and right subtrees are also balanced.

Here’s an algorithm to check whether a binary tree is balanced or not:

  1. If the root node of the tree is null, return true (an empty tree is considered balanced).
  2. Calculate the height of the left subtree of the root node by recursively calling the getHeight function on its left child.
  3. Calculate the height of the right subtree of the root node by recursively calling the getHeight function on its right child.
  4. If the absolute difference between the left and right subtree heights is greater than 1, return false (the tree is not balanced).
  5. Recursively check if both the left and right subtrees are balanced by calling the isBalanced function on them.
  6. If both subtrees are balanced, return true (the tree is balanced).
Kotlin
fun isBalanced(root: TreeNode?): Boolean {
    if (root == null) {
        return true
    }
    
    val leftHeight = getHeight(root.left)
    val rightHeight = getHeight(root.right)

    if (Math.abs(leftHeight - rightHeight) > 1) {
        return false
    }

    return isBalanced(root.left) && isBalanced(root.right)
}

fun getHeight(root: TreeNode?): Int {
    if (root == null) {
        return 0
    }
    
    return 1 + Math.max(getHeight(root.left), getHeight(root.right))
}

The isBalanced function takes a root node of a binary tree as input and returns a boolean value indicating whether the tree is balanced or not. It does this by recursively checking if the left and right subtrees are balanced and by comparing the difference in heights between the left and right subtrees.

The getHeight function is a helper function that calculates the height of the binary tree rooted at the given node using a recursive approach.

Kotlin
data class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun isBalanced(root: TreeNode?): Boolean {
    if (root == null) {
        return true
    }
    
    val leftHeight = getHeight(root.left)
    val rightHeight = getHeight(root.right)

    if (Math.abs(leftHeight - rightHeight) > 1) {
        return false
    }

    return isBalanced(root.left) && isBalanced(root.right)
}

fun getHeight(root: TreeNode?): Int {
    if (root == null) {
        return 0
    }
    
    return 1 + Math.max(getHeight(root.left), getHeight(root.right))
}

fun main() {
   	val root = TreeNode(1)
	root.left = TreeNode(2)
	root.right = TreeNode(3)
	root.left?.left = TreeNode(4)
	root.left?.right = TreeNode(5)
    root.left?.left?.left = TreeNode(6)

	val isBalanced = isBalanced(root)
	println("Is the binary tree balanced? $isBalanced")

}

In this example, the binary tree is not balanced because the left subtree has a height of 2 and the right subtree has a height of 1, resulting in a difference of 2, which is greater than 1. Therefore, the output of the program should be:

                             1
                         /      \ 
                       2        3
                    /    \   
                  4      5
                /
              6   
Is the binary tree balanced? false

Leave a Comment