Tree Terminology Root Leaf Height Depth Level in DSA Java - Execution Trace

Concept Flow - Tree Terminology Root Leaf Height Depth Level

Start at Root Node

↓

Check if Node has Children

↓

Go to Child

↓

Calculate Height & Depth

↓

Assign Level Based on Depth

↓

End

This flow shows starting from the root node, checking children to find leaves, calculating height and depth, and assigning levels.

Execution Sample

DSA Java

class Node {
  int value;
  Node left, right;
  Node(int v) { value = v; }
}

// Root is node 1, leaves are nodes with no children

Defines a simple binary tree node and identifies root and leaf nodes.

Execution Table

Step	Current Node	Is Root?	Has Children?	Is Leaf?	Depth	Height	Level
1	1	Yes	Yes	No	0	2	0
2	2	No	Yes	No	1	1	1
3	4	No	No	Yes	2	0	2
4	5	No	No	Yes	2	0	2
5	3	No	No	Yes	1	0	1
6	End	-	-	-	-	-	-

💡 All nodes visited; leaves identified; height and depth calculated; levels assigned.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
Current Node	1	2	4	5	3	-	-
Depth	0	1	2	2	1	-	-
Height	-	2	1	0	0	0	-
Level	-	0	1	2	2	1	-

Key Moments - 3 Insights

Why is the root node's depth 0 but its height 2?

Depth counts edges from root to node, so root depth is 0 (step 1). Height counts edges from node to deepest leaf, so root height is 2 because the longest path down has 2 edges (step 1).

How do we know a node is a leaf?

A leaf node has no children. In the table, nodes 4, 5, and 3 have 'Has Children?' as No and 'Is Leaf?' as Yes (steps 3, 4, 5).

What does the level represent and how is it related to depth?

Level is the depth of the node starting from 0 at root. So level equals depth (see steps 1 to 5).

Visual Quiz - 3 Questions

Look at the execution table, what is the height of node 2 at step 2?

A 0

B 2

C 1

D 3

💡 Hint

Check the 'Height' column at step 2 in the execution_table.

At which step does the node become a leaf?

A Step 3

B Step 2

C Step 1

D Step 5

💡 Hint

Look for 'Is Leaf?' marked Yes in the execution_table.

If the root node had no children, what would its height and depth be?

A Height 1, Depth 0

B Height 0, Depth 0

C Height 0, Depth 1

D Height 1, Depth 1

💡 Hint

Root depth is always 0; height is 0 if no children (leaf).

Concept Snapshot

Tree Terminology Quick Reference:
- Root: Top node, depth 0
- Leaf: Node with no children
- Depth: Edges from root to node
- Height: Edges from node to deepest leaf
- Level: Same as depth, starting at 0 for root

Full Transcript

This lesson traces tree terminology by visiting nodes step-by-step. We start at the root node with depth 0 and height calculated by longest path to a leaf. Nodes with no children are leaves. Depth counts edges from root down; height counts edges from node down to deepest leaf. Level equals depth. The execution table shows each node's properties as we visit them. Key moments clarify why root depth is zero but height can be more, how leaves are identified, and the meaning of level. The quiz tests understanding of height, leaf nodes, and root properties. This visual approach helps beginners see how tree terms relate in practice.

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