Tree Terminology Root Leaf Height Depth Level in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create the root node of a binary tree.

DSA Rust

let root = TreeNode::new([1]);

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

A0

B-1

CNone

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using None or negative values for the root node.

Using zero which might be valid but here 1 is preferred.

The root node usually starts with a value, here 1 is used as the root value.

2fill in blank

medium

Complete the code to check if a node is a leaf (no children).

DSA Rust

fn is_leaf(node: &TreeNode) -> bool {
    node.left.is_none() && node.[1].is_none()
}

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

Aroot

Bparent

Cright

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Checking parent or root instead of right child.

Using 'child' which is not a field.

A leaf node has no left or right children, so we check if right is None.

3fill in blank

hard

Fix the error in the function to calculate the height of a tree node.

DSA Rust

fn height(node: Option<&TreeNode>) -> i32 {
    if node.is_none() {
        return 0;
    }
    let node = node.unwrap();
    1 + std::cmp::max(height(node.left.as_ref()), [1])
}

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

Aheight(node.parent.as_ref())

Bheight(node.right.as_ref())

Cheight(node)

Dheight(node.left.as_ref())

Attempts:

3 left

💡 Hint

Common Mistakes

Using parent instead of right child.

Recursing on the same left child twice.

Height is the max height between left and right children plus one.

4fill in blank

hard

Fill both blanks to calculate the depth of a node given its parent depth.

DSA Rust

fn depth(node: &TreeNode, parent_depth: i32) -> i32 {
    if node.is_root() {
        return 0;
    }
    [2] parent_depth [1] 1
}

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

A+

B-

Creturn

Dlet

Attempts:

3 left

💡 Hint

Common Mistakes

Subtracting instead of adding.

Not returning the depth value.

Depth increases by 1 from parent, then return the new depth.

5fill in blank

hard

Fill all three blanks to create a function that returns the level of a node in the tree.

DSA Rust

fn level(node: &TreeNode) -> i32 {
    if node.is_root() {
        return [1];
    }
    let parent_level = level(node.[2].as_ref().unwrap());
    parent_level [3] 1
}

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

A0

Bparent

C+

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 for root level instead of 1.

Accessing left or right child instead of parent.

Subtracting instead of adding one.

Root level is 1, level is parent's level plus one, and parent is accessed via 'parent'.

Practice

1. In a tree data structure, which node is called the root?

easy

A. The topmost node with no parent

B. Any node with no children

C. A node at the deepest level

D. A node with exactly two children

Solution

1. Step 1: Understand the root node concept

   The root node is the starting point of a tree and has no parent node above it.

2. Step 2: Differentiate root from other nodes

   Leaf nodes have no children, and other nodes may have parents. Only the root has no parent.

3. Final Answer:

   The topmost node with no parent -> Option A

4. Quick Check:

   Root = top node with no parent [OK]

Hint: Root is the node with no parent, always at the top [OK]

Common Mistakes:

• Confusing root with leaf nodes
• Thinking root must have children
• Assuming root is the deepest node

2. Which of the following Rust code snippets correctly defines a leaf node in a binary tree?

easy

A. let leaf = Node { value: 5, left: Some(Box::new(Node)), right: None };

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

C. let leaf = Node { value: 5, left: None, right: None };

D. let leaf = Node { value: 5, left: Some(Box::new(Node)), right: Some(Box::new(Node)) };

Solution

1. Step 1: Identify leaf node properties

   A leaf node has no children, so both left and right must be None.

2. Step 2: Check each option for correct leaf definition

   let leaf = Node { value: 5, left: None, right: None }; sets left and right to None, correctly defining a leaf node.

3. Final Answer:

   let leaf = Node { value: 5, left: None, right: None }; -> Option C

4. Quick Check:

   Leaf node has no children (left and right None) [OK]

Hint: Leaf nodes have left and right as None [OK]

Common Mistakes:

• Setting left or right to Some(Box::new(Node)) for leaf
• Confusing struct definition with instance creation
• Missing Option wrapping for children

3. Given the following tree structure in Rust, what is the depth of node with value 4?

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

let root = Node {
    value: 1,
    left: Some(Box::new(Node {
        value: 2,
        left: Some(Box::new(Node {
            value: 4,
            left: None,
            right: None,
        })),
        right: None,
    })),
    right: Some(Box::new(Node {
        value: 3,
        left: None,
        right: None,
    })),
};

medium

A. 2

B. 0

C. 1

D. 3

Solution

1. Step 1: Understand depth definition

   Depth is the number of edges from the root to the node.

2. Step 2: Trace path from root to node 4

   Path: root(1) -> left(2) -> left(4). Number of edges = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Depth of node 4 = 2 edges from root [OK]

Hint: Count edges from root to node for depth [OK]

Common Mistakes:

• Counting nodes instead of edges
• Confusing depth with height
• Miscounting path steps

4. The following Rust code attempts to calculate the height of a binary tree node but has a bug. What is the error?

fn height(node: &Option) -> i32 {
    if let Some(n) = node {
        let left_height = height(&n.left);
        let right_height = height(&n.right);
        left_height + right_height + 1
    } else {
        0
    }
}

medium

A. The function should add 2 instead of 1

B. It should return the maximum of left and right heights, not their sum

C. The function should take &Node, not &Option

D. It should return 0 for Some nodes, not null nodes

Solution

1. Step 1: Understand height calculation logic

   Height is the longest path from node to leaf, so use max(left, right) + 1.

2. Step 2: Identify bug in code

   Code adds left_height + right_height + 1, which sums both sides incorrectly.

3. Final Answer:

   It should return the maximum of left and right heights, not their sum -> Option B

4. Quick Check:

   Height = max(left, right) + 1 [OK]

Hint: Height uses max of children heights, not sum [OK]

Common Mistakes:

• Summing left and right heights instead of max
• Confusing height with node count
• Incorrect base case return value

5. You have a tree where the root is at level 0. If a node is at level 3, what is its depth and what is the height of the subtree rooted at this node if it has no children?

hard

A. Depth = 0, Height = 0

B. Depth = 0, Height = 3

C. Depth = 3, Height = 3

D. Depth = 3, Height = 0

Solution

1. Step 1: Understand level and depth relationship

   Level and depth both count edges from root; level 0 means root, so level 3 means depth 3.

2. Step 2: Determine height of leaf node subtree

   A node with no children is a leaf, so its height is 0.

3. Final Answer:

   Depth = 3, Height = 0 -> Option D

4. Quick Check:

   Level = Depth = 3; Leaf height = 0 [OK]

Hint: Leaf node height is 0; level equals depth from root [OK]

Common Mistakes:

• Confusing height with depth
• Assuming leaf height is 1
• Mixing level numbering starting at 1