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

Tree Terminology Root Leaf Height Depth Level

📖 Scenario: Imagine you are organizing a family tree. Each person is a node. You want to understand basic terms like root (oldest ancestor), leaf (person with no children), height (longest path to a leaf), depth (distance from root), and level (depth + 1).

🎯 Goal: You will create a simple tree structure in TypeScript and write code to identify the root, leaves, calculate height, depth, and level of nodes.

📋 What You'll Learn

Create a tree with exact nodes and connections

Define a variable for the root node

Write a function to find all leaf nodes

Write a function to calculate height of the tree

Write a function to calculate depth of a given node

Print the root, leaves, height, and depth of a specific node

💡 Why This Matters

🌍 Real World

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

💼 Career

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

1

Create the Tree Structure

Create a TypeScript interface called TreeNode with properties value: string and children: TreeNode[]. Then create a tree variable called familyTree with this exact structure: value: 'Grandparent', children: two nodes with values 'Parent1' and 'Parent2'. 'Parent1' has one child 'Child1', and 'Parent2' has two children 'Child2' and 'Child3'. All children arrays must be exact.

DSA Typescript

interface TreeNode {
  value: string;
  children: TreeNode[];
}

// Create familyTree variable with the described structure
// Your code here

Hint

Define the interface first, then create the familyTree object with nested children arrays exactly as described.

2

Define the Root Node Variable

Create a constant variable called root and assign it the familyTree object.

DSA Typescript

interface TreeNode {
  value: string;
  children: TreeNode[];
}

const familyTree: TreeNode = {
  value: 'Grandparent',
  children: [
    {
      value: 'Parent1',
      children: [
        { value: 'Child1', children: [] }
      ]
    },
    {
      value: 'Parent2',
      children: [
        { value: 'Child2', children: [] },
        { value: 'Child3', children: [] }
      ]
    }
  ]
};

// Create a constant called root and assign familyTree to it
// Your code here

Hint

Just assign familyTree to a new constant called root.

3

Find All Leaf Nodes

Write a function called findLeaves that takes a TreeNode parameter called node and returns an array of strings with the values of all leaf nodes (nodes with empty children). Use recursion to explore children.

DSA Typescript

function findLeaves(node: TreeNode): string[] {
  if (node.children.length === 0) {
    return [node.value];
  }
  let leaves: string[] = [];
  for (const child of node.children) {
    leaves = leaves.concat(findLeaves(child));
  }
  return leaves;
// Write height and depth functions and print results

Hint

Check if the node has no children, then return its value in an array. Otherwise, call findLeaves recursively on each child and combine results.

4

Calculate Height, Depth and Print Results

Write a function called height that takes a TreeNode and returns the height (max distance to a leaf). Write a function called depth that takes root, a TreeNode target, and current depth number, and returns the depth of the target node. Then print the root value, the array of leaves from findLeaves(root), the height of the tree, and the depth of the node with value 'Child3'.

DSA Typescript

Hint

Height is 0 for leaf nodes, otherwise 1 + max height of children. Depth counts steps from root to target. Use recursion for both. Print results exactly as shown.

Practice

1. In a tree data structure, which node is called the root?

easy

A. A node with no children

B. The topmost node with no parent

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 a tree and has no parent node above it.

2. Step 2: Compare options with definition

   The topmost node with no parent matches the definition exactly. Other options describe leaf nodes or specific child counts.

3. Final Answer:

   The topmost node with no parent -> Option B

4. Quick Check:

   Root = topmost node with no parent [OK]

Hint: Root is always the top node without a parent [OK]

Common Mistakes:

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

2. Which of the following is the correct TypeScript syntax to define a simple tree node interface with a value and children array?

easy

A. interface TreeNode { value: number; children: TreeNode[]; }

B. interface TreeNode { value: number; children: TreeNode; }

C. interface TreeNode { value: number; children: number[]; }

D. interface TreeNode { value: number; child: TreeNode[]; }

Solution

1. Step 1: Check correct property names and types

   The children property should be an array of TreeNode objects, so type is TreeNode[].

2. Step 2: Validate each option

   interface TreeNode { value: number; children: TreeNode[]; } correctly uses 'children: TreeNode[]'. interface TreeNode { value: number; children: TreeNode; } uses single TreeNode, not array. interface TreeNode { value: number; children: number[]; } uses number array incorrectly. interface TreeNode { value: number; child: TreeNode[]; } uses wrong property name 'child'.

3. Final Answer:

   interface TreeNode { value: number; children: TreeNode[]; } -> Option A

4. Quick Check:

   Children is array of TreeNode objects [OK]

Hint: Children property must be an array of TreeNode [OK]

Common Mistakes:

• Using singular 'child' instead of 'children'
• Setting children as single object, not array
• Using wrong type like number[] for children

3. Given the following tree structure in TypeScript, what is the height of the tree?

const tree = {
  value: 1,
  children: [
    { value: 2, children: [] },
    { value: 3, children: [
      { value: 4, children: [] }
    ] }
  ]
};

medium

A. 1

B. 4

C. 3

D. 2

Solution

1. Step 1: Understand height definition

   Height is the longest path from root to any leaf node, counting edges.

2. Step 2: Trace longest path in given tree

   Root (1) to node (3) to node (4) is longest path with 2 edges, so height = 2. Counting nodes gives 3 levels, but height counts edges, so height = 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Height = longest edge count from root to leaf = 2 [OK]

Hint: Height counts edges, not nodes, from root to deepest leaf [OK]

Common Mistakes:

• Counting nodes instead of edges for height
• Confusing height with depth
• Ignoring deeper branches

4. Consider this TypeScript code snippet for calculating the depth of a node in a tree. Identify the bug:

function getDepth(node: TreeNode, root: TreeNode, depth = 0): number {
  if (node === root) return depth;
  return getDepth(node, root.children[0], depth + 1);
}

medium

A. It always checks only the first child, missing other branches

B. It never increments depth

C. It compares node and root incorrectly

D. It should return depth + 1 instead of depth

Solution

1. Step 1: Analyze recursive call logic

   The function always calls getDepth on root.children[0], ignoring other children, so it misses nodes not in first child's subtree.

2. Step 2: Understand impact on depth calculation

   This causes incorrect depth for nodes not in first child's branch, as they are never reached.

3. Final Answer:

   It always checks only the first child, missing other branches -> Option A

4. Quick Check:

   Recursion must explore all children, not just first [OK]

Hint: Check if recursion covers all children, not just one [OK]

Common Mistakes:

• Assuming single child covers whole tree
• Not handling multiple branches in recursion
• Confusing depth increment logic

5. You have a tree where each node has a level property indicating its distance from the root (root level = 0). If a node has level 3, what is its depth and height relative to the root?

hard

A. Depth = 0, Height = 3

B. Depth = 3, Height = 3

C. Depth = 3, Height depends on subtree size

D. Depth and Height both equal to 0

Solution

1. Step 1: Understand level and depth relation

   Level and depth both measure distance from root, so depth = level = 3.

2. Step 2: Understand height meaning

   Height is longest path from node down to leaf, which depends on subtree size, so height is unknown from level alone.

3. Final Answer:

   Depth = 3, Height depends on subtree size -> Option C

4. Quick Check:

   Depth = level; height varies by subtree [OK]

Hint: Level = depth; height depends on node's subtree [OK]

Common Mistakes:

• Confusing height with depth or level
• Assuming height equals level always
• Ignoring subtree size for height