Recursive tree algorithms in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start a recursive tree traversal from the root node.

Data Structures Theory

def traverse(node):
    if node is None:
        return
    print(node.value)
    traverse([1])

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

Anode.right

Bnode.left

Cnode.parent

Dnode.child

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.right instead of node.left for the first recursive call.

Trying to recurse on node.parent which leads back up the tree.

The recursive call should continue with the left child of the current node to traverse the tree.

2fill in blank

medium

Complete the code to count the total number of nodes in a binary tree recursively.

Data Structures Theory

def count_nodes(node):
    if node is None:
        return 0
    return 1 + count_nodes([1]) + count_nodes(node.right)

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

Anode.left

Bnode.parent

Cnode.child

Dnode.root

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.parent which goes upward, not downward.

Using node.child which is not a standard binary tree attribute.

To count all nodes, recursively count nodes in the left subtree and right subtree. Here, the left subtree is accessed via node.left.

3fill in blank

hard

Fix the error in the recursive function to find the height of a binary tree.

Data Structures Theory

def height(node):
    if node is None:
        return 0
    left_height = height(node.left)
    right_height = height([1])
    return 1 + max(left_height, right_height)

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

Anode.parent

Bnode.child

Cnode.root

Dnode.right

Attempts:

3 left

💡 Hint

Common Mistakes

Recursing on node.parent which causes infinite recursion or wrong results.

Using node.child which is not a valid attribute.

The height function must check both left and right children. The right child is accessed by node.right.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps each node's value to its depth in the tree.

Data Structures Theory

def map_depths(node, depth=0):
    if node is None:
        return {}
    depths = {node.value: depth}
    depths.update(map_depths([1], depth + 1))
    depths.update(map_depths([2], depth + 1))
    return depths

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

Anode.left

Bnode.right

Cnode.parent

Dnode.child

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.parent which goes upward, not downward.

Using node.child which is not a standard attribute.

To map depths correctly, recursively call the function on both left and right children, which are node.left and node.right.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps each node's value in uppercase to its depth if depth is greater than 0.

Data Structures Theory

def map_upper_depths(node, depth=0):
    if node is None:
        return {}
    depths = { [1]: [2] for k, v in map_upper_depths(node.left, depth + 1).items() if v [3] 0 }
    depths[node.value.upper()] = depth
    return depths

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

Ak.upper()

Bv

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using k instead of k.upper() for keys.

Using v < 0 which excludes all positive depths.

Using node.right instead of node.left in the recursive call.

The comprehension maps keys to uppercase (k.upper()), values as v, and filters for depths greater than 0 (v > 0).