Tree Terminology Root Leaf Height Depth Level in DSA Java

Mental Model

A tree is a structure with a starting point called root, ends called leaves, and each node has a height and depth showing its position.

Analogy: Think of a family tree: the oldest ancestor is the root, youngest children are leaves, height is how far down the longest branch goes, and depth is how far a person is from the oldest ancestor.

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

Root = top node
Leaves = C, D, E
Height = longest path down
Depth = steps from root
Level = depth + 1

Dry Run Walkthrough

Input: Tree with nodes: Root, A, B, C, D, E arranged as above

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 leaf nodes (nodes with no children)

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

Why: Leaves are nodes at the ends with no children

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

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

Why: Depth shows how far a node is from the root

Step 4: Calculate height of each node (longest path down to leaf)

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

Why: Height shows how far a node is from the farthest leaf below

Step 5: Determine level of each node (depth + 1)

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

Why: Level is a human-friendly count starting at 1 for root

Result:

Root: depth=0, height=2, level=1
Leaves: C, D, E with height=0
A and B depth=1, height=1
Levels show node distance from root starting at 1

Annotated Code

DSA Java

class TreeNode {
    String val;
    TreeNode left, right;
    TreeNode(String val) { this.val = val; }
}

public class TreeTerminology {
    // Calculate depth of each node
    static void calculateDepth(TreeNode node, int depth) {
        if (node == null) return;
        System.out.println(node.val + " depth=" + depth);
        calculateDepth(node.left, depth + 1); // go left child
        calculateDepth(node.right, depth + 1); // go right child
    }

    // Calculate height of node
    static int calculateHeight(TreeNode node) {
        if (node == null) return -1; // base case: empty child
        int leftHeight = calculateHeight(node.left); // height left
        int rightHeight = calculateHeight(node.right); // height right
        int height = 1 + Math.max(leftHeight, rightHeight);
        System.out.println(node.val + " height=" + height);
        return height;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode("Root");
        root.left = new TreeNode("A");
        root.right = new TreeNode("B");
        root.left.left = new TreeNode("C");
        root.left.right = new TreeNode("D");
        root.right.right = new TreeNode("E");

        System.out.println("Depth of nodes:");
        calculateDepth(root, 0);

        System.out.println("Height of nodes:");
        calculateHeight(root);

        System.out.println("Levels of nodes (depth + 1):");
        // Levels are depth + 1, so just print depth + 1
        printLevels(root, 0);
    }

    static void printLevels(TreeNode node, int depth) {
        if (node == null) return;
        System.out.println(node.val + " level=" + (depth + 1));
        printLevels(node.left, depth + 1);
        printLevels(node.right, depth + 1);
    }
}

calculateDepth(node.left, depth + 1); // go left child

advance to left child increasing depth by 1

calculateDepth(node.right, depth + 1); // go right child

advance to right child increasing depth by 1

int leftHeight = calculateHeight(node.left); // height left

compute height of left subtree

int rightHeight = calculateHeight(node.right); // height right

compute height of right subtree

int height = 1 + Math.max(leftHeight, rightHeight);

height is 1 plus max height of children

printLevels(node.left, depth + 1);

print level for left child (depth + 1)

printLevels(node.right, depth + 1);

print level for right child (depth + 1)

Output

Depth of nodes:

Root depth=0

A depth=1

C depth=2

D depth=2

B depth=1

E depth=2

Height of nodes:

C height=0

D height=0

A height=1

E height=0

B height=1

Root height=2

Levels of nodes (depth + 1):

Root level=1

A level=2

C level=3

D level=3

B level=2

E level=3

Complexity Analysis

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

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

vs Alternative: Iterative approaches exist but recursion is simpler and clear for tree traversal

Edge Cases

Empty tree (root is null)

No output for depth, height, or level; functions handle null safely

DSA Java

if (node == null) return;

Single node tree

Depth=0, height=0, level=1 for root node

DSA Java

if (node == null) return;

When to Use This Pattern

When a problem asks about positions or distances of nodes in a tree, think about root, leaf, depth, height, and level to describe node relationships clearly.

Common Mistakes

Mistake: Confusing depth and height values or mixing their definitions
Fix: Remember depth counts steps from root down, height counts steps from node down to farthest leaf

Mistake: Starting level count at 0 instead of 1
Fix: Level is depth + 1 to start counting levels from 1 for root

Summary

It explains the basic terms to describe nodes in a tree: root, leaf, height, depth, and level.

Use it when you need to understand or explain where nodes are in a tree and their relationships.

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 topmost node with no parent

B. A node with no children

C. Any node at the bottom 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 the tree and has no parent node above it.

2. Step 2: Identify the correct description

   Among the options, only the topmost node with no parent matches the root node definition.

3. Final Answer:

   The topmost node with no parent -> Option A

4. Quick Check:

   Root = topmost node with no parent [OK]

Hint: Root node has no parent, always at the top [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare a leaf node in Java if Node is a class representing tree nodes?

easy

A. Node leaf = new Node(); leaf.left = new Node();

B. Node leaf = null; // leaf nodes cannot be null

C. Node leaf = new Node(null, null); // no children

D. Node leaf = new Node(5); // with one child

Solution

1. Step 1: Understand leaf node definition

   A leaf node has no children, so its left and right child references should be null.

2. Step 2: Check each option for leaf node declaration

   Node leaf = new Node(5); // with one child: Node leaf = new Node(5); uses standard constructor which sets left = right = null, creating a leaf node. A adds a child. C likely causes syntax error (no such constructor). D is null, not a node.

3. Final Answer:

   Node leaf = new Node(5); // with no children -> Option D

4. Quick Check:

   Leaf node has no children = left and right null [OK]

Hint: Leaf nodes have no children, so child pointers are null [OK]

Common Mistakes:

• Assuming leaf nodes must have data only
• Creating children for leaf nodes
• Setting leaf node to null reference

3. Consider the following tree structure:

        1
       / \
      2   3
     /   / \
    4   5   6

What is the height of the tree?

medium

A. 5

B. 3

C. 2

D. 4

Solution

1. Step 1: Understand height of a tree

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

2. Step 2: Find longest path from root (1) to leaf

   Paths: 1->2->4 has 2 edges, 1->3->5 has 2 edges, 1->3->6 has 2 edges. So height = 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Longest path edges = 2 [OK]

Hint: Height = longest edges from root to leaf [OK]

Common Mistakes:

• Counting nodes instead of edges for height
• Confusing height with depth
• Counting root as height 1

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

class Node {
  int data;
  Node left, right;
  Node(int data) {
    this.data = data;
    left = right = null;
  }
}

Node root = new Node(10);
root.left = new Node(20);
root.right = new Node(30);
root.left.left = new Node(40);
root.left.right = new Node(50);
root.right.left = new Node(60);
root.right.right = new Node(70);

System.out.println(root.left.right.data);

medium

A. NullPointerException at root.left.right

B. No error, prints 50

C. Syntax error in Node class

D. Prints 60 instead of 50

Solution

1. Step 1: Trace node assignments

   root.left.right is assigned new Node(50), so it exists and has data 50.

2. Step 2: Check print statement

   Printing root.left.right.data will print 50 without error.

3. Final Answer:

   No error, prints 50 -> Option B

4. Quick Check:

   root.left.right.data = 50 [OK]

Hint: Check if node is assigned before accessing data [OK]

Common Mistakes:

• Assuming uninitialized nodes cause error here
• Confusing left and right child nodes
• Thinking print outputs 60

5. In a tree, if the root node is at level 0, what is the depth of the node with value 6 in the tree below?

        1
       / \
      2   3
     /   / \
    4   5   6

medium

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Understand depth definition

   Depth is the number of edges from the root node to the target node.

2. Step 2: Trace path from root (1) to node 6

   Path: 1 -> 3 -> 6 has 2 edges, so depth is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Edges from root to node 6 = 2 [OK]

Hint: Depth = edges from root to node [OK]

Common Mistakes:

• Counting nodes instead of edges for depth
• Confusing depth with level starting at 1
• Assuming depth equals height