Tree Terminology Root Leaf Height Depth Level in DSA C

Mental Model

A tree is like a family tree where each node is a person connected by parent-child links. We use special words to describe positions and distances in this tree.

Analogy: Imagine a family tree: the oldest ancestor is the root, people with no children are leaves, height is how tall the family tree is, depth is how far a person is from the oldest ancestor, and level is the generation number.

        [Root]
         /   \
      [A]     [B]
     /   \       \
  [C]   [D]     [E]

Root = oldest ancestor
Leaves = C, D, E (no children)
Height = longest path down (Root to C or E)
Depth = distance from Root
Level = depth + 1

Dry Run Walkthrough

Input: Tree: Root with children A and B; A has children C and D; B has child E

Goal: Identify root, leaves, height, depth, and level of each node

Step 1: Identify the root node

        [Root↑]
         /   \
      [A]     [B]
     /   \       \
  [C]   [D]     [E]

Why: Root is the starting point of the tree with no parent

Step 2: Find all leaf nodes (nodes with no children)

Leaves: [C], [D], [E]

Why: Leaves are nodes that do not have any children

Step 3: Calculate depth of each node (distance from root)

Depths: Root=0, A=1, B=1, C=2, D=2, E=2

Why: Depth counts how many steps from root to the node

Step 4: Calculate level of each node (depth + 1)

Levels: Root=1, A=2, B=2, C=3, D=3, E=3

Why: Level is the generation number starting at 1 for root

Step 5: Calculate height of the tree (max depth from root to leaf)

Height = 2 (Root to C or E path length)

Why: Height is the longest path from root down to any leaf

Result:

Root: Root
Leaves: C, D, E
Depths: Root=0, A=1, B=1, C=2, D=2, E=2
Levels: Root=1, A=2, B=2, C=3, D=3, E=3
Height: 2

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define tree node structure
typedef struct Node {
    char val;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(char val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Find height of tree
int height(Node* root) {
    if (root == NULL) return -1; // height of empty tree is -1
    int leftHeight = height(root->left); // height of left subtree
    int rightHeight = height(root->right); // height of right subtree
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; // max height + 1
}

// Print depth and level of each node
void printDepthLevel(Node* root, int depth) {
    if (root == NULL) return;
    printf("Node %c: Depth = %d, Level = %d\n", root->val, depth, depth + 1); // print depth and level
    printDepthLevel(root->left, depth + 1); // go left child
    printDepthLevel(root->right, depth + 1); // go right child
}

// Print leaves
void printLeaves(Node* root) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {
        printf("%c ", root->val); // print leaf node
    }
    printLeaves(root->left);
    printLeaves(root->right);
}

int main() {
    // Build tree from dry run example
    Node* root = newNode('R');
    root->left = newNode('A');
    root->right = newNode('B');
    root->left->left = newNode('C');
    root->left->right = newNode('D');
    root->right->right = newNode('E');

    printf("Root: %c\n", root->val);
    printf("Leaves: ");
    printLeaves(root);
    printf("\n");

    printf("Depth and Level of each node:\n");
    printDepthLevel(root, 0);

    int h = height(root);
    printf("Height of tree: %d\n", h);

    return 0;
}

if (root == NULL) return -1; // height of empty tree is -1

base case for height calculation

int leftHeight = height(root->left); // height of left subtree

recursively find left subtree height

int rightHeight = height(root->right); // height of right subtree

recursively find right subtree height

return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; // max height + 1

height is max of left/right subtree plus one for current node

printf("Node %c: Depth = %d, Level = %d\n", root->val, depth, depth + 1); // print depth and level

print current node's depth and level

printDepthLevel(root->left, depth + 1); // go left child

recurse left child with increased depth

printDepthLevel(root->right, depth + 1); // go right child

recurse right child with increased depth

if (root->left == NULL && root->right == NULL) { printf("%c ", root->val); }

print node if it is a leaf (no children)

Output

Root: R

Leaves: C D E 

Depth and Level of each node:

Node R: Depth = 0, Level = 1

Node A: Depth = 1, Level = 2

Node C: Depth = 2, Level = 3

Node D: Depth = 2, Level = 3

Node B: Depth = 1, Level = 2

Node E: Depth = 2, Level = 3

Height of tree: 2

Complexity Analysis

Time: O(n) because we visit each node once to calculate height, depth, and leaves

Space: O(h) where h is tree height due to recursion stack during traversal

vs Alternative: Compared to iterative approaches, recursion is simpler here but uses stack space; iterative may use explicit stack but same O(n) time

Edge Cases

Empty tree (root is NULL)

Height returns -1, no nodes printed for depth/level or leaves

DSA C

if (root == NULL) return -1;

Single node tree (only root)

Root is also leaf, depth 0, level 1, height 0

DSA C

if (root->left == NULL && root->right == NULL) { printf(...) }

Tree with only left children

Depth and level increase by 1 each step down left, height equals number of nodes - 1

DSA C

printDepthLevel(root->left, depth + 1);

When to Use This Pattern

When you see a problem asking about positions or distances in a tree, think about root, leaves, height, depth, and level to describe node relationships clearly.

Common Mistakes

Mistake: Confusing depth and height by mixing their definitions
Fix: Remember depth is distance from root down to node; height is distance from node down to deepest leaf

Mistake: Counting level starting from 0 instead of 1
Fix: Define level as depth + 1 so root is level 1

Summary

It defines key terms to describe tree nodes: root, leaves, height, depth, and level.

Use it when you need to understand or explain node positions and distances in a tree.

The key insight is depth measures distance from root down, height measures distance from node down to leaves, and level is depth plus one.

Practice

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

easy

A. The deepest node in the tree

B. The topmost node with no parent

C. A node with exactly two children

D. Any node with no children

Solution

1. Step 1: Understand the root node definition

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

2. Step 2: Identify the correct node type

   Nodes with no children are called leaves, not root. The root is unique and at the top.

3. Final Answer:

   The topmost node with no parent -> Option B

4. Quick Check:

   Root = topmost node with no parent [OK]

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

Common Mistakes:

• Confusing root with leaf nodes
• Thinking root has children but no parent
• Assuming root is the deepest node

2. Which of the following correctly represents a leaf node in a tree?

easy

A. A node with no children

B. The root node

C. A node with at least one child

D. A node with a parent and children

Solution

1. Step 1: Define a leaf node

   A leaf node is a node that does not have any children nodes connected below it.

2. Step 2: Check options against definition

   Only the option "A node with no children" matches the leaf node definition.

3. Final Answer:

   A node with no children -> Option A

4. Quick Check:

   Leaf = node with no children [OK]

Hint: Leaf nodes have zero children [OK]

Common Mistakes:

• Thinking leaf nodes can have children
• Confusing leaf with root node
• Assuming leaf nodes must have a parent

3. Consider the following tree structure:

        A
       / \
      B   C
     /   / \
    D   E   F

What is the height of node C?

medium

A. 0

B. 2

C. 3

D. 1

Solution

1. Step 1: Understand height of a node

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

2. Step 2: Calculate height of node C

   Node C has children E and F, both leaves (height 0). So height of C = 1 + max(0,0) = 1.

3. Step 3: Verify options

   1 says 1, but height counts edges down, so height is 1. 2 says 2, which is incorrect. Actually, height is 1.

4. Final Answer:

   1 -> Option D

5. Quick Check:

   Height of C = 1 edge to leaf [OK]

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

Common Mistakes:

• Counting nodes instead of edges for height
• Confusing height with depth
• Ignoring that leaves have height 0

4. Given the code snippet below to find the depth of a node in a tree, identify the error:

int depth(Node* root, Node* target) {
    if (root == NULL) return -1;
    if (root == target) return 0;
    int d = depth(root->left, target);
    if (d >= 0) return d + 1;
    d = depth(root->right, target);
    if (d >= 0) return d + 1;
    return -1;
}

medium

A. Function returns -1 when target is root

B. Function does not check both subtrees properly

C. Function correctly calculates depth

D. Function returns depth starting from 1 instead of 0

Solution

1. Step 1: Analyze base cases

   If root is NULL, returns -1 (not found). If root is target, returns 0 (depth zero at root).

2. Step 2: Check recursive calls

   Recursively checks left subtree; if found, adds 1. Else checks right subtree similarly. Returns -1 if not found.

3. Step 3: Confirm correctness

   This correctly calculates depth as number of edges from root to target, starting at 0 for root.

4. Final Answer:

   Function correctly calculates depth -> Option C

5. Quick Check:

   Depth function logic is correct [OK]

Hint: Depth counts edges from root; base case returns 0 [OK]

Common Mistakes:

• Returning wrong base case values
• Not checking both left and right subtrees
• Confusing depth with height

5. In a tree, the level of a node is defined as its depth plus 1. Given the tree below:

        R
       / \
      A   B
     /     \
    C       D
             \
              E

What is the level of node E?

hard

A. 4

B. 3

C. 5

D. 2

Solution

1. Step 1: Find depth of node E

   Depth is number of edges from root R to E. Path: R -> B -> D -> E has 3 edges, so depth = 3.

2. Step 2: Calculate level from depth

   Level = depth + 1 = 3 + 1 = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Level = depth + 1 = 4 [OK]

Hint: Level = depth + 1, count edges then add one [OK]

Common Mistakes:

• Counting nodes instead of edges for depth
• Forgetting to add 1 for level
• Confusing level with height