Tree Terminology Root Leaf Height Depth Level in DSA Rust - Build from Scratch

Tree Terminology: Root, Leaf, Height, Depth, Level

📖 Scenario: Imagine you are organizing a family tree. Each person is a node. The oldest ancestor is the root. People with no children are leaves. You want to understand the tree's height, depth, and levels.

🎯 Goal: You will create a simple tree structure in Rust, identify the root and leaves, calculate the height of the tree, find the depth of each node, and print the level of each node.

📋 What You'll Learn

Create a tree with nodes named exactly as specified

Use a struct called Node with fields name and children

Create a root node named "Grandparent" with two children

Add children to the children nodes to form a 3-level tree

Calculate and store the height of the tree

Calculate and store the depth of each node

Print the level of each node in the format: "Node: Level"

💡 Why This Matters

🌍 Real World

Trees are used to represent hierarchical data like family trees, file systems, and organizational charts.

💼 Career

Understanding tree terminology and traversal is essential for software development roles involving data structures, algorithms, and system design.

1

Create the Tree Structure with Root and Children

Create a struct called Node with a name field of type String and a children field which is a Vec<Node>. Then create a root node named "Grandparent" with two children named "Parent1" and "Parent2", each with empty children vectors.

DSA Rust

// Define the Node struct
// Create root node "Grandparent" with two children "Parent1" and "Parent2"
// Your code here

Hint

Use struct to define Node. Use Vec<Node> for children. Create root with two children nodes.

2

Add Children to Create a 3-Level Tree

Add two children named "Child1" and "Child2" to the "Parent1" node, and one child named "Child3" to the "Parent2" node. Keep the rest of the tree structure unchanged.

DSA Rust

// Add children "Child1" and "Child2" to "Parent1"
// Add child "Child3" to "Parent2"
// Your code here

Hint

Inside Parent1's children vector, add Child1 and Child2. Inside Parent2's children vector, add Child3.

3

Calculate the Height of the Tree

Write a recursive function called height that takes a reference to a Node and returns an usize representing the height of the tree. The height of a leaf node is 0. Use this function to calculate the height of the root node and store it in a variable called tree_height.

DSA Rust

struct Node {
    name: String,
    children: Vec,
}

fn main() {
    let root = Node {
        name: String::from("Grandparent"),
        children: vec![
            Node {
                name: String::from("Parent1"),
                children: vec![
                    Node {
                        name: String::from("Child1"),
                        children: vec![],
                    },
                    Node {
                        name: String::from("Child2"),
                        children: vec![],
                    },
                ],
            },
            Node {
                name: String::from("Parent2"),
                children: vec![
                    Node {
                        name: String::from("Child3"),
                        children: vec![],
                    },
                ],
            },
        ],
    };

    // Define a recursive function height
    // Calculate tree_height using height(root)
    // Your code here
}

Hint

Use recursion: height is 0 if no children, else 1 plus max height of children.

4

Calculate Depth and Print Levels of Each Node

Write a recursive function called print_levels that takes a reference to a Node and a usize depth starting at 0. It should print each node's name and its level (depth) in the format: "NodeName: Level". Call this function with the root node and depth 0 to print all nodes and their levels.

DSA Rust

struct Node {
    name: String,
    children: Vec,
}

fn height(node: &Node) -> usize {
    if node.children.is_empty() {
        0
    } else {
        1 + node.children.iter().map(|child| height(child)).max().unwrap()
    }
}

fn main() {
    let root = Node {
        name: String::from("Grandparent"),
        children: vec![
            Node {
                name: String::from("Parent1"),
                children: vec![
                    Node {
                        name: String::from("Child1"),
                        children: vec![],
                    },
                    Node {
                        name: String::from("Child2"),
                        children: vec![],
                    },
                ],
            },
            Node {
                name: String::from("Parent2"),
                children: vec![
                    Node {
                        name: String::from("Child3"),
                        children: vec![],
                    },
                ],
            },
        ],
    };

    let tree_height = height(&root);

    // Define print_levels function
    // Call print_levels(root, 0)
    // Your code here
}

Hint

Print the node's name and depth. Then call the function recursively on children with depth + 1.

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