Check if Binary Tree is Balanced in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

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

beginner

Why is checking the height difference important in a balanced binary tree?

Because a large height difference means one side is much deeper, which can cause inefficient operations like search or insert.

intermediate

What is the time complexity of a naive approach that checks balance by computing height separately for each node?

The naive approach has O(n²) time complexity because height is recalculated for each node leading to repeated work.

intermediate

How can we optimize the balance check to run in O(n) time?

By computing height and balance status together in one recursive function, returning -1 if unbalanced to stop early.

beginner

In Go, what is a simple way to represent a binary tree node?

Using a struct with an integer value and pointers to left and right child nodes, e.g., type TreeNode struct { Val int; Left, Right *TreeNode }.

What is the maximum allowed height difference between left and right subtrees for a balanced binary tree node?

A 2

B 1

C 0

D 3

A balanced binary tree node must have left and right subtree heights differing by at most 1.

Which approach improves the balance check to O(n) time complexity?

A Use a recursive function that returns height and balance status together

B Use iterative BFS traversal

C Traverse only left subtree

D Calculate height separately for each node

Returning height and balance status together avoids repeated height calculations, making it O(n).

In Go, what type is used to represent child nodes in a binary tree struct?

A string

B int

C *TreeNode

D bool

Child nodes are pointers to TreeNode structs, allowing recursive tree structures.

If a node's left subtree height is 3 and right subtree height is 5, is the node balanced?

A No

B Yes

C Only if left subtree is full

D Only if right subtree is full

Height difference is 2, which is more than 1, so the node is not balanced.

What does a recursive function return to indicate an unbalanced subtree in the optimized approach?

A 0

B 1

C nil

D -1

Returning -1 signals that the subtree is unbalanced, allowing early termination.

Explain how to check if a binary tree is balanced using a single recursive function.

Think about combining height calculation and balance check in one step.

Describe the difference between the naive and optimized approaches to check if a binary tree is balanced.

Focus on how many times height is computed.