Check if Binary Tree is Balanced in DSA Typescript - 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 balance important in binary trees?

Balanced trees keep operations like search, insert, and delete efficient, usually in O(log n) time, by avoiding long branches.

intermediate

What is the main idea behind the efficient algorithm to check if a binary tree is balanced?

Use a bottom-up approach that returns the height of subtrees and checks balance at the same time, stopping early if imbalance is found.

intermediate

What is the time complexity of the efficient balanced tree check algorithm?

O(n), where n is the number of nodes, because each node is visited once during the height and balance check.

intermediate

In TypeScript, what type of value can be used to indicate an unbalanced subtree during recursion?

A special value like -1 can be returned to indicate the subtree is unbalanced, allowing early stopping.

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

A 1

B 2

C 0

D 3

A balanced binary tree requires the height difference to be at most 1.

Which approach is more efficient to check if a binary tree is balanced?

A Bottom-up recursion returning height and balance

B Top-down checking height repeatedly

C Level order traversal only

D Inorder traversal only

Bottom-up recursion checks balance and height in one pass, avoiding repeated height calculations.

What does a return value of -1 typically indicate in the balanced tree check algorithm?

A Leaf node found

B Subtree is balanced

C Height of subtree

D Subtree is unbalanced

-1 signals that the subtree is unbalanced, so recursion can stop early.

What is the time complexity of the naive top-down approach to check if a binary tree is balanced?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

Naive approach recalculates height for each node, leading to O(n^2) time.

If a binary tree has only one node, is it balanced?

A Only if it has children

B Yes

C Depends on the node value

D No

A single node tree is balanced by definition.

Explain how the bottom-up recursion method checks if a binary tree is balanced.

Think about how height and balance information is passed up from children to parent.

Describe the difference in time complexity between the naive and efficient methods to check if a binary tree is balanced.

Consider how many times each node's height is computed.