Check if Binary Tree is Balanced in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Balance Check on Simple Tree

What is the output of the following Go code that checks if a binary tree is balanced?

DSA Go

package main
import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isBalanced(root *TreeNode) bool {
    var check func(node *TreeNode) int
    check = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := check(node.Left)
        if left == -1 {
            return -1
        }
        right := check(node.Right)
        if right == -1 {
            return -1
        }
        if abs(left-right) > 1 {
            return -1
        }
        if left > right {
            return left + 1
        }
        return right + 1
    }
    return check(root) != -1
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}
    fmt.Println(isBalanced(root))
}

A false

B true

C runtime error

D compilation error

💡 Hint

Think about the height difference between left and right subtrees for each node.

The tree is balanced because for every node, the height difference between left and right subtrees is at most 1.

The function returns true.

❓ Predict Output

intermediate

Output of Balance Check on Unbalanced Tree

What is the output of the following Go code that checks if a binary tree is balanced?

DSA Go

package main
import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isBalanced(root *TreeNode) bool {
    var check func(node *TreeNode) int
    check = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := check(node.Left)
        if left == -1 {
            return -1
        }
        right := check(node.Right)
        if right == -1 {
            return -1
        }
        if abs(left-right) > 1 {
            return -1
        }
        if left > right {
            return left + 1
        }
        return right + 1
    }
    return check(root) != -1
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Left.Left = &TreeNode{Val: 3}
    root.Left.Left.Left = &TreeNode{Val: 4}
    fmt.Println(isBalanced(root))
}

A compilation error

B true

C runtime error

D false

💡 Hint

Check the height difference at the root node.

The tree is unbalanced because the left subtree is much deeper than the right subtree (which is nil).

The function returns false.

🧠 Conceptual

advanced

Understanding the Balance Check Algorithm

Which statement best describes how the balance check algorithm works in the given code?

A It only checks leaf nodes to determine if the tree is balanced.

B It traverses the tree in level order and counts nodes to decide balance.

C It calculates the height of left and right subtrees and returns false immediately if difference is more than 1.

D It uses a stack to store nodes and checks balance after traversal.

💡 Hint

Think about how the function returns -1 to indicate imbalance.

The algorithm uses recursion to get heights of left and right subtrees.

If the difference is more than 1, it returns -1 to indicate imbalance immediately.

🔧 Debug

advanced

Identify the Bug in Balance Check Code

What error will the following code produce when run?

DSA Go

package main
import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isBalanced(root *TreeNode) bool {
    var check func(node *TreeNode) int
    check = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := check(node.Left)
        right := check(node.Right)
        if abs(left-right) > 1 {
            return -1
        }
        if left > right {
            return left + 1
        }
        return right + 1
    }
    return check(root) != -1
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Left.Left = &TreeNode{Val: 3}
    root.Left.Left.Left = &TreeNode{Val: 4}
    fmt.Println(isBalanced(root))
}

A Incorrect balance result due to missing imbalance check propagation

B No error, outputs false

C Stack overflow due to infinite recursion

D No error, outputs true

💡 Hint

Check if the function stops checking when imbalance is found in subtrees.

The code does not check if left or right subtree returned -1 (imbalance) before continuing.

This causes incorrect results because imbalance is not propagated up.

🚀 Application

expert

Count Balanced Subtrees in a Binary Tree

Given a binary tree, which code snippet correctly counts how many subtrees are balanced?

DSA Go

package main
import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func countBalancedSubtrees(root *TreeNode) int {
    count := 0
    var check func(node *TreeNode) int
    check = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := check(node.Left)
        if left == -1 {
            return -1
        }
        right := check(node.Right)
        if right == -1 {
            return -1
        }
        if abs(left-right) > 1 {
            return -1
        }
        count++
        if left > right {
            return left + 1
        }
        return right + 1
    }
    check(root)
    return count
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}
    fmt.Println(countBalancedSubtrees(root))
}

A 5

B 3

C 4

D 2

💡 Hint

Count every subtree that returns a valid height (not -1).

The balanced subtrees are the leaf nodes (4,5,3), the subtree rooted at 2, and the whole tree rooted at 1.

Total balanced subtrees = 5.