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

Concept Flow - Tree Terminology Root Leaf Height Depth Level

Start at Root Node

↓

Check if Node has Children

↓

Go to Child

↓

Repeat for all Children

↓

Calculate Height and Depth

↓

Assign Level Based on Depth

Start from the root node, explore children to find leaves, then calculate height, depth, and level for each node.

Execution Sample

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
}

Defines a simple tree node with a value and list of children.

Execution Table

Step	Current Node	Children Present?	Action	Height	Depth	Level
1	A (Root)	Yes	Go to children B and C	?	0	0
2	B	Yes	Go to children D and E	?	1	1
3	D	No	Leaf node found	0	2	2
4	E	No	Leaf node found	0	2	2
5	B	After children processed	Calculate height = max(0,0)+1=1	1	1	1
6	C	No	Leaf node found	0	1	1
7	A	After children processed	Calculate height = max(1,0)+1=2	2	0	0
8	End	-	All nodes processed	-	-	-

💡 All nodes visited, heights and depths calculated, levels assigned based on depth.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
Current Node	-	A	B	D	E	B	C	A	-
Height	-	?	?	0	0	1	0	2	-
Depth	-	0	1	2	2	1	1	0	-
Level	-	0	1	2	2	1	1	0	-

Key Moments - 3 Insights

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

Depth counts edges from root down, so root is 0. Height counts edges down to farthest leaf, so root height is max child height + 1 (2 here). See execution_table rows 1 and 7.

Why do leaf nodes have height 0?

Leaf nodes have no children, so height is 0 by definition. This is shown in execution_table rows 3, 4, and 6.

How is level related to depth?

Level is the same as depth here, counting edges from root. Both are assigned together as shown in execution_table columns Depth and Level.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the height of node D?

A 0

B 1

C 2

D Undefined

💡 Hint

Check the Height column at Step 3 in execution_table.

At which step does the condition 'Children Present?' become No for node C?

A Step 2

B Step 6

C Step 4

D Step 7

💡 Hint

Look at the Current Node and Children Present? columns in execution_table.

If node B had one more child, how would the height of node A change?

A It would decrease

B It would increase by 1

C It would stay the same

D Cannot determine

💡 Hint

Height depends on the maximum child height, see calculation in Step 7 of execution_table.

Concept Snapshot

Tree Terminology Quick Reference:
- Root: Top node, depth 0
- Leaf: Node with no children, height 0
- Depth: Edges from root to node
- Height: Edges from node to deepest leaf
- Level: Same as depth here
- Height(node) = max height(children) + 1

Full Transcript

This visual execution traces tree terminology concepts. Starting at the root node A, we check if it has children. Since it does, we move to children B and C. Node B has children D and E, which are leaves with height 0. We calculate heights bottom-up: leaves have height 0, their parents have height 1, and root has height 2. Depth counts edges from root down, so root is 0, its children 1, and leaves 2. Level matches depth. This helps understand how root, leaf, height, depth, and level relate in a tree.

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 definition

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

2. Step 2: Compare options with definition

   The topmost node with no parent matches this definition exactly; other options describe leaf or internal nodes.

3. Final Answer:

   The topmost node with no parent -> Option A

4. Quick Check:

   Root = topmost node with no parent [OK]

Hint: Root is always the very first node, no parent above it [OK]

Common Mistakes:

• Confusing root with leaf nodes
• Thinking root must have children
• Assuming root is at the bottom

2. Which of the following is the correct way to describe a leaf node in a tree?

easy

A. The root node

B. A node with at least one child

C. A node with no children

D. A node with exactly one child

Solution

1. Step 1: Define leaf node

   A leaf node is a node that does not have any children; it is at the end of a branch.

2. Step 2: Match options to definition

   Only A node with no children states the node has no children, which matches the leaf node definition.

3. Final Answer:

   A node with no children -> Option C

4. Quick Check:

   Leaf = node with no children [OK]

Hint: Leaf nodes have zero children, always at branch ends [OK]

Common Mistakes:

• Thinking leaf nodes have children
• Confusing leaf with root
• Assuming leaf nodes must have one child

3. Consider the following tree structure:

        A
       / \
      B   C
     /   / \
    D   E   F

What is the height of node B?

medium

A. 1

B. 2

C. 3

D. 0

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 B

   Node B has one child D which is a leaf. The longest path from B to leaf is B->D with 1 edge.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Height of B = 1 edge to leaf D [OK]

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

Common Mistakes:

• Counting nodes instead of edges
• Confusing height with depth
• Counting path to root instead of leaf

4. Given this tree:

        X
       / \
      Y   Z
     / 
    W  

What is the depth of node W?
Note: Depth is the number of edges from the root to the node.

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Understand depth definition

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

2. Step 2: Count edges from root X to W

   Path is X -> Y -> W, which has 2 edges.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Depth of W = 2 edges from root [OK]

Hint: Depth counts edges up from root to node [OK]

Common Mistakes:

• Counting nodes instead of edges
• Confusing depth with height
• Starting count from 1 instead of 0 edges

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

        M
       / \
      N   O
         / \
        P   Q

What is the level of node P?

hard

A. 2

B. 1

C. 4

D. 3

Solution

1. Step 1: Calculate depth of node P

   Path from root M to P is M -> O -> P, which has 2 edges, so depth = 2.

2. Step 2: Calculate level using formula

   Level = depth + 1 = 2 + 1 = 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Level = depth + 1 = 3 [OK]

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

Common Mistakes:

• Using depth as level without adding 1
• Counting nodes incorrectly
• Confusing level with height