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.