Tree Terminology Root Leaf Height Depth Level in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the tree traversal showing node levels?

Given a simple binary tree, what will be the printed levels of each node?

DSA Rust

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

fn print_levels(node: &Option<Box<Node>>, level: usize) {
    if let Some(n) = node {
        println!("{}: Level {}", n.value, level);
        print_levels(&n.left, level + 1);
        print_levels(&n.right, level + 1);
    }
}

fn main() {
    let tree = Some(Box::new(Node {
        value: 1,
        left: Some(Box::new(Node {
            value: 2,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 3,
            left: None,
            right: None,
        })),
    }));
    print_levels(&tree, 0);
}

A

1: Level 1
2: Level 1
3: Level 1

B

1: Level 1
2: Level 2
3: Level 2

C

1: Level 0
2: Level 0
3: Level 0

D

1: Level 0
2: Level 1
3: Level 1

💡 Hint

Remember, root node starts at level 0, children increase level by 1.

The root node (value 1) is at level 0. Its children (2 and 3) are at level 1.

🧠 Conceptual

intermediate

What is the height of a leaf node in a tree?

In tree terminology, what is the height of a leaf node?

A 0

B 1

C Depends on the depth

D Undefined

💡 Hint

Height is the number of edges on the longest path from the node down to a leaf.

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

🔧 Debug

advanced

Why does this code print incorrect depth values?

Consider this Rust code that tries to print the depth of each node but prints wrong values. Identify the bug.

DSA Rust

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

fn print_depth(node: &Option<Box<Node>>, depth: usize) {
    if let Some(n) = node {
        println!("{}: Depth {}", n.value, depth);
        print_depth(&n.left, depth);
        print_depth(&n.right, depth);
    }
}

fn main() {
    let tree = Some(Box::new(Node {
        value: 10,
        left: Some(Box::new(Node {
            value: 20,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 30,
            left: None,
            right: None,
        })),
    }));
    print_depth(&tree, 0);
}

A The root node should start with depth 1, not 0.

B The function should print height, not depth.

C The depth parameter is not incremented when recursing to children.

D The Option<Box<Node>> should be replaced with Rc<Node>.

💡 Hint

Check how the depth parameter changes in recursive calls.

The depth parameter must increase by 1 when moving to child nodes to reflect correct depth.

🚀 Application

advanced

Calculate the height of a binary tree in Rust

What is the output of this Rust function that calculates the height of a binary tree?

DSA Rust

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

fn height(node: &Option<Box<Node>>) -> usize {
    match node {
        None => 0,
        Some(n) => {
            let left_height = height(&n.left);
            let right_height = height(&n.right);
            1 + std::cmp::max(left_height, right_height)
        }
    }
}

fn main() {
    let tree = Some(Box::new(Node {
        value: 5,
        left: Some(Box::new(Node {
            value: 3,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 8,
            left: Some(Box::new(Node {
                value: 7,
                left: None,
                right: None,
            })),
            right: None,
        })),
    }));
    println!("Height: {}", height(&tree));
}

A Height: 1

B Height: 3

C Height: 2

D Height: 4

💡 Hint

Height counts nodes on the longest path from root to leaf.

The longest path is 5 -> 8 -> 7, which has 3 nodes, so height is 3.

🧠 Conceptual

expert

What is the level of the root node in a tree?

In tree terminology, what is the level of the root node?

A 0

B 1

C Depends on the tree height

D Undefined

💡 Hint

Level counts edges from the root to the node.

The root node is at level 0 because it has no 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