Tree Terminology Root Leaf Height Depth Level in DSA Javascript

Mental Model

A tree is like a family tree where each person is connected to parents and children. We use special names for the top person, the bottom people, and how far each person is from the top.

Analogy: Imagine a family tree: the oldest ancestor is the root, the youngest children with no kids 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)        (F)

Legend:
- Root: A
- Leaves: D, E, F
- Height: longest path from root to leaf
- Depth: distance from root to a node
- Level: depth + 1

Dry Run Walkthrough

Input: Tree with nodes: A(root), B and C children of A, D and E children of B, F child of C

Goal: Understand root, leaf, height, depth, and level for each node

Step 1: Identify the root node

Root: A
Tree: A -> B, C -> D, E, F

Why: Root is the top node with no parent

Step 2: Identify leaf nodes

Leaves: D, E, F
Tree: A -> B, C -> D, E, F

Why: Leaves have no children

Step 3: Calculate height of tree

Height = 3 (A to D or A to F path length)

Why: Height is longest path from root to any leaf

Step 4: Calculate depth of node E

Depth(E) = 2 (A -> B -> E)

Why: Depth is number of edges from root to node

Step 5: Calculate level of node E

Level(E) = 3 (depth + 1)

Why: Level counts nodes from root as 1

Result:

Root: A
Leaves: D, E, F
Height: 3
Depth(E): 2
Level(E): 3

Annotated Code

DSA Javascript

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

// Function to find height of tree
function treeHeight(node) {
  if (!node) return 0;
  if (node.children.length === 0) return 1; // leaf node
  let heights = node.children.map(child => treeHeight(child));
  return 1 + Math.max(...heights);
}

// Function to find depth of a node given root
function findDepth(root, target, depth = 0) {
  if (!root) return -1;
  if (root.value === target) return depth;
  for (let child of root.children) {
    let d = findDepth(child, target, depth + 1);
    if (d !== -1) return d;
  }
  return -1;
}

// Function to find leaves
function findLeaves(node, leaves = []) {
  if (!node) return leaves;
  if (node.children.length === 0) leaves.push(node.value);
  for (let child of node.children) {
    findLeaves(child, leaves);
  }
  return leaves;
}

// Driver code
const A = new TreeNode('A');
const B = new TreeNode('B');
const C = new TreeNode('C');
const D = new TreeNode('D');
const E = new TreeNode('E');
const F = new TreeNode('F');

A.children.push(B, C);
B.children.push(D, E);
C.children.push(F);

console.log('Root:', A.value);
console.log('Leaves:', findLeaves(A).join(', '));
console.log('Height:', treeHeight(A));
const target = 'E';
const depthE = findDepth(A, target);
console.log(`Depth(${target}):`, depthE);
console.log(`Level(${target}):`, depthE + 1);

if (node.children.length === 0) return 1; // leaf node

return 1 for leaf node height base case

let heights = node.children.map(child => treeHeight(child));

recursively get heights of all children

return 1 + Math.max(...heights);

height is 1 plus max height among children

if (root.value === target) return depth;

found target node, return current depth

let d = findDepth(child, target, depth + 1);

search children increasing depth by 1

if (node.children.length === 0) leaves.push(node.value);

collect leaf nodes with no children

Output

Root: A

Leaves: D, E, F

Height: 3

Depth(E): 2

Level(E): 3

Complexity Analysis

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

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

vs Alternative: Iterative approaches may use queues but still visit all nodes, so similar O(n) time

Edge Cases

Empty tree (root is null)

Height is 0, no leaves, depth queries return -1

DSA Javascript

if (!node) return 0;

Single node tree

Root is also leaf, height is 1, depth of root is 0

DSA Javascript

if (node.children.length === 0) return 1;

Target node not found for depth

Returns -1 indicating node not present

DSA Javascript

return -1;

When to Use This Pattern

When a problem involves hierarchical data or family-like relationships, recognize tree terminology to navigate and measure nodes effectively.

Common Mistakes

Mistake: Confusing depth and level by forgetting level is depth plus one
Fix: Remember level counts nodes starting at 1 for root, so level = depth + 1

Mistake: Assuming leaf nodes have children or missing them
Fix: Check children length equals zero to identify leaves

Summary

Defines key tree terms: root (top node), leaf (no children), height (longest path from root), depth (distance from root), and level (depth plus one).

Use when working with tree structures to understand node positions and tree shape.

The aha moment is seeing the tree like a family tree with generations and distances from the oldest ancestor.

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