Recursive tree algorithms in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Recursive Tree Traversal

Consider a binary tree where each node has a value and two children (left and right). Which of the following best describes the order of nodes visited in a preorder traversal?

A Visit the root node, then the right subtree, and finally the left subtree.

B Recursively traverse the left subtree, then the right subtree, and visit the root node last.

C Visit the root node first, then recursively traverse the left subtree, then the right subtree.

D Recursively traverse the left subtree first, then visit the root node, then traverse the right subtree.

💡 Hint

Preorder means you visit the root before its children.

In preorder traversal, the root node is visited first, then the left subtree is traversed recursively, followed by the right subtree.

📋 Factual

intermediate

Base Case in Recursive Tree Algorithms

What is the typical base case condition in a recursive function that processes nodes of a binary tree?

A When the current node is null (or None), stop the recursion.

B When the current node has two children, stop the recursion.

C When the current node's value is zero, stop the recursion.

D When the current node is a leaf node, continue recursion.

💡 Hint

Think about when there is no node to process.

The base case for recursive tree functions is usually when the node is null, meaning there is no node to process, so recursion stops.

🚀 Application

advanced

Calculating Tree Height Recursively

Given a binary tree, which recursive approach correctly calculates its height (the number of edges on the longest path from root to a leaf)?

Data Structures Theory

def tree_height(node):
    if node is None:
        return -1
    left_height = tree_height(node.left)
    right_height = tree_height(node.right)
    return 1 + max(left_height, right_height)

A Returns -1 for null nodes and adds 1 plus the maximum height of left and right subtrees.

B Returns 0 for null nodes and adds 1 plus the minimum height of left and right subtrees.

C Returns 0 for null nodes and adds 1 plus the maximum height of left and right subtrees.

D Returns 1 for null nodes and adds 1 plus the sum of left and right subtree heights.

💡 Hint

Height of an empty tree is usually defined as -1 or 0 depending on convention.

For height as number of edges, empty tree height is -1. Returns -1 for null nodes and adds 1 plus the maximum height of left and right subtrees correctly computes it.

🔍 Analysis

advanced

Analyzing Recursive Tree Search Complexity

What is the time complexity of a recursive depth-first search (DFS) on a binary tree with n nodes?

A O(1), because recursion stops as soon as the target is found.

B O(log n), because the tree is divided in half at each step.

C O(n^2), because each node is compared with every other node.

D O(n), because each node is visited exactly once.

💡 Hint

Consider how many nodes the algorithm visits in the worst case.

DFS visits every node once, so the time complexity is linear in the number of nodes, O(n).

❓ Reasoning

expert

Effect of Tree Shape on Recursive Traversal Depth

Consider two binary trees each with 15 nodes: one is perfectly balanced, and the other is skewed (all nodes have only one child). How does the maximum recursion depth during a full traversal compare between these two trees?

A Both trees have the same maximum recursion depth of 15 because they have the same number of nodes.

B The balanced tree has a maximum recursion depth of about 4, while the skewed tree has a maximum recursion depth of 15.

C The balanced tree has a maximum recursion depth of 15, while the skewed tree has a depth of about 4.

D Both trees have a maximum recursion depth of about 4 because recursion depth depends on the height of the tree.

💡 Hint

Think about how tree height affects recursion depth.

The balanced tree has height about log2(15) ≈ 4, so recursion depth is about 4. The skewed tree is like a linked list with height 15, so recursion depth is 15.

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