BST balancing problem in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify if a binary search tree (BST) is balanced by checking the height difference of its subtrees.

Data Structures Theory

def is_balanced(node):
    if node is None:
        return True
    left_height = height(node.left)
    right_height = height(node.right)
    if abs(left_height [1] right_height) > 1:
        return False
    return is_balanced(node.left) and is_balanced(node.right)

Drag options to blanks, or click blank then click option'

A-

B+

C==

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction inside abs()

Using equality operator instead of subtraction

The function uses abs(left_height - right_height) to find the absolute difference in heights between left and right subtrees. If this difference is more than 1, the tree is unbalanced.

2fill in blank

medium

Complete the code to perform a left rotation on a node in a BST to help balance the tree.

Data Structures Theory

def left_rotate(x):
    y = x.right
    x.right = y.[1]
    y.left = x
    return y

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning y.right instead of y.left

Confusing left and right children

In a left rotation, the right child of node x becomes the new root, and x becomes the left child of that node. The left subtree of y moves to be the right subtree of x.

3fill in blank

hard

Fix the error in the code that checks the balance factor of a node in an AVL tree.

Data Structures Theory

def balance_factor(node):
    return height(node.left) [1] height(node.right)

Drag options to blanks, or click blank then click option'

A/

B*

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction

Using multiplication or division

The balance factor is the difference between the height of the left subtree and the right subtree. It is calculated by subtracting height(node.right) from height(node.left).

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps each node's value to its balance factor in a BST.

Data Structures Theory

balance_factors = {node.value: height(node.[1]) [2] height(node.right) for node in nodes}

Drag options to blanks, or click blank then click option'

Aleft

B-

C+

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction

Using 'parent' instead of 'left' for subtree access

The balance factor is calculated by subtracting the height of the right subtree from the height of the left subtree for each node.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that stores the height of each node's left subtree, the node's value, and the height of its right subtree.

Data Structures Theory

node_info = {node.[1]: {"left_height": height(node.left), "value": node.[2], "right_height": height(node.[3])} for node in nodes}

Drag options to blanks, or click blank then click option'

Avalue

Cright

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'left' instead of 'right' for the right subtree height

Using incorrect keys for dictionary

The dictionary keys are the node values accessed by node.value. The right subtree height is accessed by node.right.

Practice

1. What is the main reason to balance a Binary Search Tree (BST)?

easy

A. To keep operations like search, insert, and delete efficient

B. To increase the number of nodes in the tree

C. To make the tree look symmetrical

D. To store duplicate values easily

Solution

1. Step 1: Understand BST operations

   BST operations like search, insert, and delete depend on tree height for speed.

2. Step 2: Effect of balancing

   Balancing keeps the tree height minimal, making these operations faster.

3. Final Answer:

   To keep operations like search, insert, and delete efficient -> Option A

4. Quick Check:

   Balanced BST = Efficient operations [OK]

Hint: Balanced BST means faster search and updates [OK]

Common Mistakes:

• Thinking balancing increases nodes
• Believing balancing is just for looks
• Confusing balancing with allowing duplicates

2. Which of the following is a correct step in balancing a BST?

easy

A. Get sorted keys and rebuild tree with middle key as root

B. Delete all leaf nodes

C. Insert nodes in ascending order

D. Swap left and right children of all nodes

Solution

1. Step 1: Recall balancing method

   Balancing involves sorting keys and rebuilding the tree.

2. Step 2: Middle key as root

   Choosing the middle key as root ensures minimal height and balance.

3. Final Answer:

   Get sorted keys and rebuild tree with middle key as root -> Option A

4. Quick Check:

   Middle key root = Balanced BST [OK]

Hint: Middle key root rebuilds balanced BST [OK]

Common Mistakes:

• Inserting nodes in sorted order causes unbalance
• Deleting leaf nodes does not balance tree
• Swapping children does not guarantee balance

3. Given a BST with nodes inserted in this order: 10, 5, 1, 7, 40, 50, what is the height of the tree after balancing it?

medium

A. 2

B. 5

C. 4

D. 3

Solution

1. Step 1: List nodes in sorted order

   Sorted keys: 1, 5, 7, 10, 40, 50.

2. Step 2: Build balanced BST

   Middle key is 10 (root), left subtree with 1,5,7, right subtree with 40,50.

3. Step 3: Calculate height

   Height is 3 (longest path from root to leaf has 3 edges): root(10), children(5,40), grandchildren(1,7,50).

4. Final Answer:

   3 -> Option D

5. Quick Check:

   Balanced BST height = 3 [OK]

Hint: Balanced BST height ~ log2(n) [OK]

Common Mistakes:

• Counting unbalanced height
• Choosing wrong middle key
• Miscounting tree levels

4. You tried to balance a BST by just swapping left and right children of every node. What is the main problem with this approach?

medium

A. It sorts the keys incorrectly

B. It deletes all leaf nodes accidentally

C. It may create an unbalanced tree or violate BST property

D. It duplicates nodes in the tree

Solution

1. Step 1: Understand swapping effect

   Swapping children flips the tree but does not reorder keys.

2. Step 2: Check BST property

   BST requires left child keys < node < right child keys; swapping breaks this.

3. Final Answer:

   It may create an unbalanced tree or violate BST property -> Option C

4. Quick Check:

   Swapping children ≠ balancing BST [OK]

Hint: Swapping children breaks BST order, not balance [OK]

Common Mistakes:

• Thinking swapping sorts keys
• Assuming swapping deletes nodes
• Believing swapping duplicates nodes

5. You have a BST with keys [3, 8, 10, 15, 20, 25, 30] inserted in that order. To balance it, you extract the sorted keys and rebuild the tree. Which key should be the root of the balanced BST?

medium

A. 10

B. 15

C. 20

D. 8

Solution

1. Step 1: Sort keys

   Keys are already sorted: 3, 8, 10, 15, 20, 25, 30.

2. Step 2: Find middle key

   Middle key is the 4th element (index 3): 15.

3. Step 3: Use middle key as root

   Root = 15 ensures balanced left and right subtrees.

4. Final Answer:

   15 -> Option B

5. Quick Check:

   Middle key root = 15 [OK]

Hint: Middle element of sorted keys is balanced root [OK]

Common Mistakes:

• Choosing first or last key as root
• Picking a key not in the middle
• Ignoring sorted order