Recursive tree algorithms in Data Structures Theory - Time & Space Complexity

Time Complexity: Recursive tree algorithms

O(n)

Understanding Time Complexity

When working with recursive tree algorithms, it's important to understand how the number of steps grows as the tree gets bigger.

We want to know how the time needed changes when the tree has more nodes.

Scenario Under Consideration

Analyze the time complexity of the following recursive tree traversal.

function traverse(node) {
  if (node === null) return;
  process(node.value);
  traverse(node.left);
  traverse(node.right);
}
    

This code visits every node in a binary tree once, processing its value and then calling itself on the left and right children.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The recursive calls to traverse each child node.
• How many times: Once for every node in the tree.

How Execution Grows With Input

As the tree grows, the number of nodes increases, and the function visits each node once.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The work grows directly with the number of nodes, so doubling nodes roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Recursive tree algorithms always take exponential time because of repeated calls."

[OK] Correct: In simple traversals like this, each node is visited once, so the time grows linearly, not exponentially.

Interview Connect

Understanding how recursion visits each node helps you explain and analyze many tree problems clearly and confidently.

Self-Check

"What if the tree is very unbalanced and looks like a linked list? How would the time complexity change?"

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