Check if Binary Tree is Balanced in DSA Go - Build from Scratch

Check if Binary Tree is Balanced

📖 Scenario: You are working on a system that manages hierarchical data like company departments or family trees. To keep the system efficient, you need to check if the binary tree structure is balanced. A balanced tree means the left and right subtrees of every node differ in height by no more than 1.

🎯 Goal: Build a Go program that creates a binary tree, sets up a helper function to check balance, implements the logic to check if the tree is balanced, and finally prints the result.

📋 What You'll Learn

Create a binary tree with the exact structure given

Add a helper function to calculate height and check balance

Implement the logic to check if the tree is balanced

Print true if balanced, false otherwise

💡 Why This Matters

🌍 Real World

Balanced binary trees are used in databases, file systems, and network routing to keep operations fast and efficient.

💼 Career

Understanding tree balance is important for software engineers working on performance-critical applications and data structure optimization.

1

Create the Binary Tree Structure

Define a struct called Node with value as int, and pointers left and right to Node. Then create a variable root representing the root node with value 1, its left child with value 2, and right child with value 3. The left child of node 2 should have value 4, and the right child of node 2 should have value 5. The right child of node 3 should have value 6.

DSA Go

// Define Node struct and create the binary tree as described
// Your code here

Hint

Start by defining the Node struct with the fields. Then create the root node and assign its children as pointers.

2

Add Helper Function to Check Height and Balance

Add a function called checkHeight that takes a pointer to Node and returns an int height and a bool indicating if the subtree is balanced. If the node is nil, return height 0 and balanced true. Recursively get left and right subtree heights and balance. If either subtree is unbalanced or the height difference is more than 1, return balanced false. Otherwise, return the height as max of left and right plus 1 and balanced true.

DSA Go

package main

import "fmt"

type Node struct {
    value int
    left  *Node
    right *Node
}

// Add checkHeight function below
// Your code here

func main() {
    root := &Node{value: 1}
    root.left = &Node{value: 2}
    root.right = &Node{value: 3}
    root.left.left = &Node{value: 4}
    root.left.right = &Node{value: 5}
    root.right.right = &Node{value: 6}
}

Hint

Use recursion to get height and balance status from left and right children. Compare heights and balance flags to decide current node's balance.

3

Implement Function to Check if Tree is Balanced

Add a function called isBalanced that takes a pointer to Node and returns a bool. It should call checkHeight on the node and return only the balance boolean.

DSA Go

func isBalanced(root *Node) bool {
    _, balanced := checkHeight(root)
    return balanced
    // Print the balance status below
    // Your code here

Hint

Use the helper checkHeight function and return the balance boolean only.

4

Print if the Tree is Balanced

In the main function, add a line to print the result of calling isBalanced with root. It should print true if the tree is balanced, otherwise false.

DSA Go

Hint

Use fmt.Println to print the result of isBalanced(root).

Practice

1. What does it mean for a binary tree to be balanced?

easy

A. The height difference between left and right subtrees of every node is at most 1

B. All nodes have two children

C. The tree has the same number of nodes on left and right

D. The tree is a complete binary tree

Solution

1. Step 1: Understand the balance condition

   A balanced binary tree means for every node, the height difference between its left and right subtree is at most 1.

2. Step 2: Compare options with definition

   The height difference between left and right subtrees of every node is at most 1 matches the definition exactly. Other options describe different tree properties.

3. Final Answer:

   The height difference between left and right subtrees of every node is at most 1 -> Option A

4. Quick Check:

   Balanced tree = height difference ≤ 1 [OK]

Hint: Balance means height difference ≤ 1 at every node [OK]

Common Mistakes:

• Confusing balanced with complete tree
• Thinking balanced means equal number of nodes
• Assuming all nodes must have two children

2. Which Go function signature correctly represents a function to check if a binary tree is balanced?

easy

A. func isBalanced(root *TreeNode) bool

B. func isBalanced(root TreeNode) int

C. func checkBalance(root *TreeNode) string

D. func balanced(root *TreeNode) void

Solution

1. Step 1: Identify correct parameter and return types

   The function should take a pointer to the root node and return a boolean indicating balanced or not.

2. Step 2: Match options with correct signature

   func isBalanced(root *TreeNode) bool matches: input is *TreeNode pointer, output is bool. Others have wrong return types or parameter types.

3. Final Answer:

   func isBalanced(root *TreeNode) bool -> Option A

4. Quick Check:

   Input pointer, output bool = correct signature [OK]

Hint: Check function returns bool and takes *TreeNode pointer [OK]

Common Mistakes:

• Passing TreeNode by value instead of pointer
• Returning int or string instead of bool
• Using void (no return) for a check function

3. What will the output be for the following Go code snippet that checks if a binary tree is balanced?

package main
import "fmt"

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

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    if leftHeight == -1 || rightHeight == -1 || abs(leftHeight-rightHeight) > 1 {
        return -1
    }
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

func isBalanced(root *TreeNode) bool {
    return height(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.Left.Left = &TreeNode{Val: 5}
    fmt.Println(isBalanced(root))
}

medium

A. Compilation error

B. true

C. false

D. Runtime panic

Solution

1. Step 1: Analyze tree structure and height function

   The tree is left-heavy: left subtree has height 3, right subtree height 1 at root. Difference is 2 > 1, so height returns -1.

2. Step 2: Check isBalanced return value

   isBalanced returns height(root) != -1, which is false here because height returned -1.

3. Final Answer:

   false -> Option C

4. Quick Check:

   Height difference > 1 means balanced = false [OK]

Hint: Height returns -1 if unbalanced; check != -1 for balanced [OK]

Common Mistakes:

• Assuming tree is balanced without checking height difference
• Confusing return values of height function
• Ignoring left-heavy subtree depth

4. Identify the bug in this Go function that checks if a binary tree is balanced:

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return false
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    if abs(leftHeight - rightHeight) > 1 {
        return false
    }
    return isBalanced(root.Left) && isBalanced(root.Right)
}

medium

A. Uses incorrect logical operator in return

B. Returns false for empty tree instead of true

C. Missing base case for leaf nodes

D. Does not check height difference correctly

Solution

1. Step 1: Check base case for empty tree

   Function returns false if root is nil, but empty tree is balanced, so should return true.

2. Step 2: Verify other logic correctness

   Height difference check and recursive calls are correct. Only base case return is wrong.

3. Final Answer:

   Returns false for empty tree instead of true -> Option B

4. Quick Check:

   Empty tree is balanced, so base case must return true [OK]

Hint: Empty tree is balanced; base case must return true [OK]

Common Mistakes:

• Returning false for nil root
• Not checking both subtrees recursively
• Confusing logical AND with OR in recursion

5. Given a binary tree, how can you efficiently check if it is balanced without recalculating heights multiple times?

hard

A. Calculate height of left and right subtrees separately for each node

B. Check balance only at the root node

C. Use breadth-first traversal to count nodes at each level

D. Use a bottom-up recursion that returns height or -1 if unbalanced

Solution

1. Step 1: Understand naive approach inefficiency

   Calculating height separately for each node causes repeated work, leading to O(n²) time.

2. Step 2: Use bottom-up recursion for efficiency

   Return height if balanced, else -1 to stop early. This avoids repeated height calculations, achieving O(n) time.

3. Final Answer:

   Use a bottom-up recursion that returns height or -1 if unbalanced -> Option D

4. Quick Check:

   Bottom-up recursion avoids repeated height calls [OK]

Hint: Return -1 on unbalanced during height calc to stop early [OK]

Common Mistakes:

• Recalculating heights multiple times causing slow code
• Checking balance only at root misses subtree imbalance
• Using BFS which doesn't help with height difference