Tree Terminology Root Leaf Height Depth Level in DSA C++ - 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 structure by finding the root, leaves, height, depth, and level of each person.

🎯 Goal: You will create a simple tree structure in C++. Then, you will identify the root node, find all leaf nodes, calculate the height of the tree, and determine the depth and level of each node.

📋 What You'll Learn

Create a tree using nodes with integer values

Identify the root node

Find all leaf nodes

Calculate the height of the tree

Calculate the depth and level of each node

Print the root, leaves, height, depth, and level information

💡 Why This Matters

🌍 Real World

Trees are used in many real-world applications like family trees, file systems, and organizational charts. Understanding tree terminology helps in navigating and managing these structures.

💼 Career

Knowledge of tree structures and their properties is essential for software developers, especially those working with databases, compilers, and hierarchical data.

1

Create the Tree Nodes

Create a struct called Node with an int data and two pointers left and right. Then create nodes with these exact values and connections: root node with data = 1, left child with data = 2, right child with data = 3, left child of node 2 with data = 4, right child of node 2 with data = 5. Connect them properly to form the tree.

DSA C++

// Define struct Node with int data, Node* left, Node* right
// Create nodes 1, 2, 3, 4, 5 and connect as described

Hint

Define a struct with data and two child pointers. Then create nodes and connect them using arrow -> operator.

2

Add Helper Variables for Traversal

Create an integer variable called height and set it to 0. Also create a function prototype for int calculateHeight(Node* node) that will calculate the height of the tree.

DSA C++

#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

int calculateHeight(Node* node);

int main() {
    Node* root = new Node{1, nullptr, nullptr};
    root->left = new Node{2, nullptr, nullptr};
    root->right = new Node{3, nullptr, nullptr};
    root->left->left = new Node{4, nullptr, nullptr};
    root->left->right = new Node{5, nullptr, nullptr};

    int height = 0;
    // Your code here

    return 0;
}

Hint

Declare the variable height inside main(). Write the function prototype above main().

3

Implement Height Calculation and Find Leaves

Implement the function int calculateHeight(Node* node) that returns 0 if node is nullptr. Otherwise, it returns 1 plus the maximum height of the left and right subtrees. Then, in main(), set height to calculateHeight(root). Also, write a function void printLeaves(Node* node) that prints the data of all leaf nodes (nodes with no children). Call printLeaves(root) in main().

DSA C++

#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

int calculateHeight(Node* node) {
    // Your code here
}

void printLeaves(Node* node) {
    // Your code here
}

int main() {
    Node* root = new Node{1, nullptr, nullptr};
    root->left = new Node{2, nullptr, nullptr};
    root->right = new Node{3, nullptr, nullptr};
    root->left->left = new Node{4, nullptr, nullptr};
    root->left->right = new Node{5, nullptr, nullptr};

    int height = 0;

    height = calculateHeight(root);
    printLeaves(root);

    return 0;
}

Hint

Use recursion to find height by checking left and right subtree heights. For leaves, print nodes with no children.

4

Calculate and Print Depth and Level of Each Node

Write a function void printDepthLevel(Node* node, int depth) that prints each node's data, its depth, and its level. The root node has depth 0 and level 1. For each child, depth increases by 1 and level is depth + 1. Call printDepthLevel(root, 0) in main(). Finally, print the root node data and the height of the tree with these exact lines: cout << "Root: " << root->data << endl; and cout << "Height: " << height << endl;.

DSA C++

#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

int calculateHeight(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    int leftHeight = calculateHeight(node->left);
    int rightHeight = calculateHeight(node->right);
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

void printLeaves(Node* node) {
    if (node == nullptr) {
        return;
    }
    if (node->left == nullptr && node->right == nullptr) {
        cout data left);
    printLeaves(node->right);
}

void printDepthLevel(Node* node, int depth) {
    // Your code here
}

int main() {
    Node* root = new Node{1, nullptr, nullptr};
    root->left = new Node{2, nullptr, nullptr};
    root->right = new Node{3, nullptr, nullptr};
    root->left->left = new Node{4, nullptr, nullptr};
    root->left->right = new Node{5, nullptr, nullptr};

    int height = 0;

    height = calculateHeight(root);
    printLeaves(root);

    printDepthLevel(root, 0);
    cout data << endl;
    cout << "Height: " << height << endl;

    return 0;
}

Hint

Use recursion to print each node's data, depth, and level. Remember root depth is 0 and level is depth + 1.

Practice

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

easy

A. A node with exactly two children

B. A node with no children

C. The topmost node with no parent

D. Any node at the bottom level

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, but root has no parent. Bottom level nodes are leaves or internal nodes, not necessarily root.

3. Final Answer:

   The topmost node with no parent -> Option C

4. Quick Check:

   Root = topmost node with no parent [OK]

Hint: Root is the only node without a parent [OK]

Common Mistakes:

• Confusing root with leaf node
• Thinking root must have children
• Assuming root is at bottom level

2. Which of the following is the correct way to declare a simple binary tree node struct in C++?

easy

A. struct Node { int data; Node* left; Node* right; };

B. struct Node { int data; Node left; Node right; };

C. struct Node { int data; Node* left; int right; };

D. struct Node { int data; int left; int right; };

Solution

1. Step 1: Check pointer usage for child nodes

   Child nodes must be pointers to Node to allow recursive structure.

2. Step 2: Validate data types of members

   Data is int, left and right are pointers to Node, so struct Node { int data; Node* left; Node* right; }; is correct.

3. Final Answer:

   struct Node { int data; Node* left; Node* right; }; -> Option A

4. Quick Check:

   Child nodes use pointers in struct [OK]

Hint: Child nodes must be pointers to Node type [OK]

Common Mistakes:

• Using Node instead of Node* for children
• Mixing int and Node types for children
• Missing semicolon at struct end

3. Consider the following tree:

        10
       /  \
      5    15
     /    /  \
    3    12  20

What is the height of the node with value 5?

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Understand height definition

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

2. Step 2: Calculate height of node 5

   Node 5 has left child 3 (leaf). Longest path from 5 to leaf is 5 -> 3, which is 1 edge. Height of 3 is 0. Height of 5 = 1 + max height of children = 1 + 0 = 1. However, node 5 has no right child, so max height is 1. So height is 1. But the question asks for height of node 5. Since 3 is leaf (height 0), height of 5 is 1. But 2 says 2, which is incorrect. So correct answer is 1 (1).

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Height = edges to deepest leaf = 1 [OK]

Hint: Height counts edges down to deepest leaf [OK]

Common Mistakes:

• Counting nodes instead of edges
• Confusing height with depth
• Ignoring missing right child

4. Given the following code snippet, what is the error?

struct Node {
  int data;
  Node* left;
  Node* right;
};

Node* root = new Node{10, nullptr, nullptr};
root->left = new Node{5, nullptr, nullptr};
root->left->left = new Node{3, nullptr, nullptr};
root->right = new Node{15, nullptr, nullptr};
root->right->right = new Node{20, nullptr, nullptr};
root->right->left = 12;

medium

A. Incorrect initialization of root node

B. Missing semicolon after struct definition

C. Using nullptr instead of NULL

D. Assigning int 12 to a Node* pointer

Solution

1. Step 1: Analyze the last assignment

   Line root->right->left = 12; assigns integer 12 to a pointer Node* left, which is invalid.

2. Step 2: Check pointer assignment rules

   Pointers must be assigned addresses or nullptr, not raw integers.

3. Final Answer:

   Assigning int 12 to a Node* pointer -> Option D

4. Quick Check:

   Pointer must hold address, not int [OK]

Hint: Pointers cannot hold raw integers [OK]

Common Mistakes:

• Ignoring type mismatch in assignment
• Thinking nullptr and NULL difference causes error
• Overlooking semicolon presence

5. In a tree, the depth of a node is defined as the number of edges from the root to that node. Given the tree:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

What is the depth of node 7 and what is its level?

hard

A. Depth = 3, Level = 3

B. Depth = 3, Level = 4

C. Depth = 4, Level = 3

D. Depth = 4, Level = 4

Solution

1. Step 1: Calculate depth of node 7

   Path from root (1) to 7 is 1 -> 3 -> 5 -> 7, which has 3 edges, so depth = 3.

2. Step 2: Calculate level of node 7

   Level is depth + 1, so level = 3 + 1 = 4.

3. Final Answer:

   Depth = 3, Level = 4 -> Option B

4. Quick Check:

   Level = depth + 1 = 4 [OK]

Hint: Level = depth + 1 always [OK]

Common Mistakes:

• Confusing depth with level
• Counting nodes instead of edges for depth
• Starting depth count from 0 or 1 incorrectly