Count Total Nodes in Binary Tree in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the total number of nodes in the binary tree.

DSA Rust

fn count_nodes(root: &Option<Box<TreeNode>>) -> i32 {
    match root {
        None => 0,
        Some(node) => 1 + count_nodes(&node.left) + count_nodes(&node[1])
    }
}

Drag options to blanks, or click blank then click option'

A.parent

B.left

C.value

D.right

Attempts:

3 left

💡 Hint

Common Mistakes

Using '.left' again instead of '.right' causes counting only left subtree twice.

Using '.value' or '.parent' is incorrect because they are not child nodes.

We count nodes by adding 1 for the current node plus counts of left and right subtrees. The blank should be '.right' to access the right child.

2fill in blank

medium

Complete the code to create a new TreeNode with given value.

DSA Rust

fn new_node(val: i32) -> Box<TreeNode> {
    Box::new(TreeNode {
        value: val,
        left: None,
        [1]: None,
    })
}

Drag options to blanks, or click blank then click option'

Aparent

Bright

Cchild

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'parent' or 'child' which are not fields in the TreeNode struct.

Using 'node' which is not a field name.

A TreeNode has 'left' and 'right' children. To initialize the right child as empty, use 'right: None'.

3fill in blank

hard

Fix the error in the recursive call to count nodes in the right subtree.

DSA Rust

fn count_nodes(root: &Option<Box<TreeNode>>) -> i32 {
    match root {
        None => 0,
        Some(node) => 1 + count_nodes(&node.left) + count_nodes(&node[1])
    }
}

Drag options to blanks, or click blank then click option'

A.leftt

B.left

C.right

D.value

Attempts:

3 left

💡 Hint

Common Mistakes

Typo in field name like '.leftt' causes compile error.

Using '.value' instead of child node fields.

The correct field name for the right child is '.right'. '.leftt' is a typo and '.value' is not a child node.

4fill in blank

hard

Fill both blanks to create a function that counts nodes only if the node's value is greater than 0.

DSA Rust

fn count_positive_nodes(root: &Option<Box<TreeNode>>) -> i32 {
    match root {
        None => 0,
        Some(node) => {
            let count_left = count_positive_nodes(&node[1]);
            let count_right = count_positive_nodes(&node[2]);
            if node.value > 0 { 1 + count_left + count_right } else { count_left + count_right }
        }
    }
}

Drag options to blanks, or click blank then click option'

A.left

B.right

C.parent

D.value

Attempts:

3 left

💡 Hint

Common Mistakes

Using '.parent' or '.value' which are not child nodes.

Swapping left and right fields.

To count nodes in left and right subtrees, use '.left' and '.right' respectively.

5fill in blank

hard

Fill all three blanks to create a function that counts nodes with values less than a given threshold.

DSA Rust

fn count_nodes_less_than(root: &Option<Box<TreeNode>>, threshold: i32) -> i32 {
    match root {
        None => 0,
        Some(node) => {
            let left_count = count_nodes_less_than(&node[1], threshold);
            let right_count = count_nodes_less_than(&node[2], threshold);
            if node.value [3] threshold { 1 + left_count + right_count } else { left_count + right_count }
        }
    }
}

Drag options to blanks, or click blank then click option'

A.left

B.right

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<' changes the condition logic.

Using '.parent' or '.value' instead of child nodes.

We recurse on left and right children using '.left' and '.right'. To check if node value is less than threshold, use '<'.

Practice

1. What does the function to count total nodes in a binary tree do?

easy

A. It returns the sum of all node values.

B. It returns the total number of nodes in the tree.

C. It returns the height of the tree.

D. It returns the number of leaf nodes only.

Solution

1. Step 1: Understand the function's purpose

   The function is designed to count how many nodes exist in the entire binary tree.

2. Step 2: Differentiate from other tree properties

   Counting nodes is different from calculating height, sum of values, or counting leaves.

3. Final Answer:

   It returns the total number of nodes in the tree. -> Option B

4. Quick Check:

   Counting nodes = total nodes [OK]

Hint: Count all nodes, not just leaves or height [OK]

Common Mistakes:

• Confusing node count with tree height
• Counting only leaf nodes
• Summing node values instead of counting

2. Which Rust code snippet correctly defines a binary tree node struct for counting nodes?

easy

A. struct Node { value: i32, left: Option, right: Option }

B. struct Node { value: i32, left: Node, right: Node }

C. struct Node { value: i32, left: &Node, right: &Node }

D. struct Node { value: i32, left: Box<Node>, right: Box<Node> }

Solution

1. Step 1: Understand Rust ownership and recursive types

   Recursive types like binary trees require using Box and Option to allow nullable pointers and heap allocation.

2. Step 2: Identify correct struct syntax

   Option allows left and right to be either None or Some(Box<Node>), which is correct for binary trees.

3. Final Answer:

   struct Node { value: i32, left: Option, right: Option } -> Option A

4. Quick Check:

   Use Option for nullable children [OK]

Hint: Use Option for child nodes in Rust [OK]

Common Mistakes:

• Using direct Node type causing infinite size error
• Using references without lifetimes
• Not wrapping children in Option

3. What is the output of this Rust function call counting nodes in the given tree?

fn count_nodes(root: &Option) -> i32 {
    match root {
        None => 0,
        Some(node) => 1 + count_nodes(&node.left) + count_nodes(&node.right),
    }
}

// Tree structure:
//       10
//      /  \
//     5    15
//          /
//         12

let root = Some(Box::new(Node {
    value: 10,
    left: Some(Box::new(Node { value: 5, left: None, right: None })),
    right: Some(Box::new(Node {
        value: 15,
        left: Some(Box::new(Node { value: 12, left: None, right: None })),
        right: None,
    })),
}));

println!("{}", count_nodes(&root));

medium

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Count nodes in each subtree

   Root node (10) counts as 1. Left subtree has 1 node (5). Right subtree has 2 nodes (15 and 12).

2. Step 2: Sum all nodes

   Total nodes = 1 (root) + 1 (left) + 2 (right) = 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   1 + 1 + 2 = 4 [OK]

Hint: Add 1 for root plus counts of left and right [OK]

Common Mistakes:

• Counting only leaf nodes
• Forgetting to add root node
• Miscounting subtree nodes

4. Identify the error in this Rust function that counts nodes in a binary tree:

fn count_nodes(root: Option) -> i32 {
    if root.is_none() {
        return 0;
    }
    1 + count_nodes(root.unwrap().left) + count_nodes(root.unwrap().right)
}

medium

A. Using unwrap() twice consumes the value causing a move error.

B. The function should return usize, not i32.

C. The base case should return 1 instead of 0.

D. The function should use references instead of ownership.

Solution

1. Step 1: Understand ownership and unwrap behavior

   Calling unwrap() consumes the Option, so calling it twice on the same variable causes a move error.

2. Step 2: Identify correct fix

   Store the result of unwrap() in a variable to avoid multiple moves or use references.

3. Final Answer:

   Using unwrap() twice consumes the value causing a move error. -> Option A

4. Quick Check:

   unwrap() moves value; multiple calls cause error [OK]

Hint: Call unwrap() once, store result before use [OK]

Common Mistakes:

• Calling unwrap() multiple times on same Option
• Ignoring ownership and move semantics
• Returning wrong base case value

5. Given a binary tree where each node has a value and pointers to left and right children, how would you modify the counting function to count only nodes with values greater than 10? Choose the correct Rust function implementation.

hard

A. fn count_nodes_gt_10(root: &Option) -> i32 {
if root.is_none() {
return 0;
}
let node = root.unwrap();
if node.value > 10 {
1 + count_nodes_gt_10(&node.left) + count_nodes_gt_10(&node.right)
} else {
0
}
}

B. fn count_nodes_gt_10(root: &Option) -> i32 {
match root {
None => 0,
Some(node) => 1 + count_nodes_gt_10(&node.left) + count_nodes_gt_10(&node.right),
}
}

C. fn count_nodes_gt_10(root: &Option) -> i32 {
match root {
None => 0,
Some(node) => {
let count_left = count_nodes_gt_10(&node.left);
let count_right = count_nodes_gt_10(&node.right);
if node.value > 10 {
1 + count_left + count_right
} else {
count_left + count_right
}
}
}
}

D. fn count_nodes_gt_10(root: &Option) -> i32 {
match root {
None => 0,
Some(node) => if node.value > 10 { 1 } else { 0 },
}
}

Solution

1. Step 1: Traverse entire tree recursively

   We must visit every node to check its value and count accordingly.

2. Step 2: Count nodes with value > 10 correctly

   If node's value is greater than 10, add 1 plus counts from left and right subtrees; else add only counts from children.

3. Final Answer:

   Function that adds 1 only if node.value > 10, else sums children counts. -> Option C

4. Quick Check:

   Count nodes with value > 10 recursively [OK]

Hint: Add 1 only if node value > 10, else sum children [OK]

Common Mistakes:

• Counting all nodes regardless of value
• Returning 0 when node value <= 10 without counting children
• Not traversing entire tree