Recursive tree algorithms in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a recursive tree algorithm?

A recursive tree algorithm is a method that solves problems by breaking a tree into smaller parts (subtrees) and solving each part using the same process until reaching simple cases.

beginner

Why are recursive algorithms natural for trees?

Because trees are made of nodes connected to smaller trees (subtrees), recursion fits well by processing each node and then calling itself on its children.

beginner

What is the base case in a recursive tree algorithm?

The base case is the simplest part of the tree, often a leaf node or an empty subtree, where the recursion stops and returns a direct answer.

intermediate

Give an example of a problem solved by recursive tree algorithms.

Calculating the height of a tree: the algorithm finds the height of each child subtree recursively and returns the maximum height plus one for the current node.

beginner

How does recursion help in traversing a tree?

Recursion allows visiting each node by calling the same function on child nodes, making it easy to explore all parts of the tree systematically.

What is the first step in a recursive tree algorithm?

A Process all child nodes first

B Ignore the children of the node

C Return the final answer immediately

D Check if the current node is a base case

The algorithm first checks if the current node is a base case to decide whether to stop or continue recursion.

Which of these is NOT a typical base case in recursive tree algorithms?

A Leaf node

B Root node with children

C Empty subtree

D Single node tree

The root node with children is not a base case because it usually requires further recursive calls on its children.

What does a recursive tree algorithm usually return after processing child nodes?

A A combined result based on child results

B Nothing

C Only the first child's result

D The original input

It combines the results from child nodes to form the answer for the current node.

Which problem can be solved using recursive tree algorithms?

A Calculating the sum of array elements

B Sorting a list of numbers

C Finding the maximum depth of a tree

D Searching in a flat list

Finding the maximum depth of a tree is a classic problem solved by recursive tree algorithms.

What is the main advantage of using recursion on trees?

A It simplifies handling complex tree structures

B It avoids using any memory

C It always runs faster than loops

D It does not require a base case

Recursion naturally fits tree structures and simplifies the code for complex problems.

Explain how a recursive tree algorithm works using the example of calculating tree height.

Think about how you find the tallest branch by checking smaller branches first.

Describe why recursion is a good fit for tree data structures.

Consider how trees naturally break down into smaller parts.

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