Tree Terminology Root Leaf Height Depth Level in DSA Javascript - Build from Scratch

Understanding Tree Terminology: Root, Leaf, Height, Depth, Level

📖 Scenario: Imagine you are organizing a family tree. Each person is connected to their parents and children, forming a tree structure. To understand this tree better, you need to identify the root (oldest ancestor), leaves (family members with no children), and calculate the height, depth, and level of each member.

🎯 Goal: You will create a simple tree structure in JavaScript and write code to identify the root, leaves, and calculate height, depth, and level for each node.

📋 What You'll Learn

Create a tree object with nodes representing family members

Identify the root node

Identify leaf nodes

Calculate the height of the tree

Calculate the depth and level of each node

Print the results clearly

💡 Why This Matters

🌍 Real World

Trees are used in family trees, file systems, organizational charts, and many other hierarchical data representations.

💼 Career

Understanding tree terminology and traversal is essential for software developers working with data structures, databases, and algorithms.

1

Create the Tree Structure

Create a variable called familyTree representing this tree structure as nested objects: John is the root with children Mary and David. Mary has children Anna and James. David has no children.

DSA Javascript

// Your code here

Hint

Use nested objects with name and children arrays to represent the tree.

2

Identify Root and Leaf Nodes

Create a variable called root and set it to familyTree. Then create a function called findLeaves that takes a node and returns an array of names of all leaf nodes (nodes with empty children arrays).

DSA Javascript

const familyTree = {
  name: 'John',
  children: [
    {
      name: 'Mary',
      children: [
        { name: 'Anna', children: [] },
        { name: 'James', children: [] }
      ]
    },
    {
      name: 'David',
      children: []
    }
  ]
};

// Create root variable
// Create findLeaves function
// Your code here

Hint

Root is the top node. Leaves have no children. Use recursion to find leaves.

3

Calculate Height, Depth, and Level

Create a function called calculateHeight that returns the height of the tree starting from a given node. Then create a function called assignDepthAndLevel that takes a node and a depth number (start with 0) and adds depth and level properties to each node. Level is depth + 1.

DSA Javascript

const familyTree = {
  name: 'John',
  children: [
    {
      name: 'Mary',
      children: [
        { name: 'Anna', children: [] },
        { name: 'James', children: [] }
      ]
    },
    {
      name: 'David',
      children: []
    }
  ]
};

const root = familyTree;

function findLeaves(node) {
  if (node.children.length === 0) {
    return [node.name];
  }
  let leaves = [];
  for (const child of node.children) {
    leaves = leaves.concat(findLeaves(child));
  }
  return leaves;
}

// Create calculateHeight function
// Create assignDepthAndLevel function
// Your code here

Hint

Height is longest path to leaf. Depth starts at 0 for root. Level is depth + 1.

4

Print Tree Information

Call assignDepthAndLevel on root. Then print the root name, the array of leaf names from findLeaves(root), and the height of the tree from calculateHeight(root). Finally, print each node's name with its depth and level using a function printNodeInfo that traverses the tree.

DSA Javascript

const familyTree = {
  name: 'John',
  children: [
    {
      name: 'Mary',
      children: [
        { name: 'Anna', children: [] },
        { name: 'James', children: [] }
      ]
    },
    {
      name: 'David',
      children: []
    }
  ]
};

const root = familyTree;

function findLeaves(node) {
  if (node.children.length === 0) {
    return [node.name];
  }
  let leaves = [];
  for (const child of node.children) {
    leaves = leaves.concat(findLeaves(child));
  }
  return leaves;
}

function calculateHeight(node) {
  if (node.children.length === 0) {
    return 0;
  }
  let heights = node.children.map(calculateHeight);
  return 1 + Math.max(...heights);
}

function assignDepthAndLevel(node, depth = 0) {
  node.depth = depth;
  node.level = depth + 1;
  for (const child of node.children) {
    assignDepthAndLevel(child, depth + 1);
  }
}

// Call assignDepthAndLevel on root
// Print root name
// Print leaves array
// Print height
// Print each node's name with depth and level
// Your code here

Hint

Use console.log to print the root, leaves, height, and each node's depth and level.

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