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).

Practice

1. What is the main purpose of using recursion in tree algorithms?

easy

A. To convert the tree into a list without visiting nodes

B. To avoid using any base case in the algorithm

C. To break down the problem into smaller subproblems on child nodes

D. To only process the root node and ignore children

Solution

1. Step 1: Understand recursion in trees

   Recursion helps by calling the same function on smaller parts, like child nodes, to solve the whole tree problem.

2. Step 2: Identify the main goal

   The main goal is to break down the problem into smaller subproblems on child nodes, making it easier to solve.

3. Final Answer:

   To break down the problem into smaller subproblems on child nodes -> Option C

4. Quick Check:

   Recursion = smaller subproblems [OK]

Hint: Recursion splits tree tasks into child node problems [OK]

Common Mistakes:

• Thinking recursion skips child nodes
• Ignoring the need for a base case
• Assuming recursion processes only the root

2. Which of the following is the correct base case for a recursive tree traversal function?

easy

A. If the current node is null, return immediately

B. If the current node has children, stop recursion

C. Always call recursion without any condition

D. Return the value of the root node only

Solution

1. Step 1: Identify the base case role

   The base case stops recursion when there is no node to process, preventing infinite calls.

2. Step 2: Choose the correct base case

   If the current node is null (empty), the function should return immediately to stop recursion.

3. Final Answer:

   If the current node is null, return immediately -> Option A

4. Quick Check:

   Base case = node is null [OK]

Hint: Base case stops recursion on empty nodes [OK]

Common Mistakes:

• Stopping recursion when children exist
• Not having any base case causing infinite recursion
• Returning only root value without recursion

3. Consider this recursive function to count nodes in a binary tree:

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

What will count_nodes(root) return if the tree has 3 nodes?

medium

A. 6

B. 1

C. 0

D. 3

Solution

1. Step 1: Understand the function logic

   The function returns 0 if the node is empty. Otherwise, it counts 1 for the current node plus counts from left and right children recursively.

2. Step 2: Apply to a tree with 3 nodes

   Each node adds 1, so total count is 3 nodes.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count nodes = 3 [OK]

Hint: Count adds 1 per node recursively [OK]

Common Mistakes:

• Confusing count with sum of values
• Forgetting to add 1 for current node
• Returning count of edges instead of nodes

4. Identify the error in this recursive tree traversal code:

def traverse(node):
    if node.left is None and node.right is None:
        return
    traverse(node.left)
    traverse(node.right)

medium

A. Missing base case for when node is None

B. Recursion should only call on node.right

C. Function should return node value instead of None

D. No error, code is correct

Solution

1. Step 1: Check base case correctness

   The code only stops recursion if both children are None, but does not handle when node itself is None.

2. Step 2: Identify missing base case

   Without checking if node is None, calling traverse(None) will cause an error.

3. Final Answer:

   Missing base case for when node is None -> Option A

4. Quick Check:

   Base case must check node is None [OK]

Hint: Always check if node is None before recursion [OK]

Common Mistakes:

• Only checking children but not node itself
• Assuming leaf nodes stop recursion safely
• Ignoring None checks causing runtime errors

5. You want to calculate the height of a binary tree using recursion. Which approach correctly computes the height?

hard

A. Return sum of heights of left and right subtrees without adding 1

B. Return 1 + max(height of left subtree, height of right subtree), base case height 0 for empty node

C. Return 1 for every node without recursion

D. Return height as number of leaf nodes

Solution

1. Step 1: Understand height definition

   Height is the longest path from root to a leaf, so it depends on max height of subtrees plus 1 for current node.

2. Step 2: Choose correct recursive formula

   Return 1 + max(height(left), height(right)) with base case 0 for empty nodes correctly computes height.

3. Final Answer:

   Return 1 + max(height of left subtree, height of right subtree), base case height 0 for empty node -> Option B

4. Quick Check:

   Height = 1 + max subtree heights [OK]

Hint: Height = 1 + max height of children [OK]

Common Mistakes:

• Adding heights instead of max
• Ignoring base case for empty nodes
• Counting leaf nodes instead of height