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.