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.