Tree Terminology Root Leaf Height Depth Level in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the root of a tree?

The root is the topmost node of a tree. It has no parent and is the starting point of the tree.

beginner

Define a leaf node in a tree.

A leaf node is a node that has no children. It is at the end of a branch.

intermediate

What does the height of a node represent in a tree?

Height of a node is the number of edges on the longest path from that node down to a leaf.

intermediate

Explain the depth of a node in a tree.

Depth of a node is the number of edges from the root node down to that node.

beginner

What is the level of a node in a tree?

Level of a node is its depth plus one. The root is at level 1, its children at level 2, and so on.

Which node in a tree has no parent?

A Child

B Leaf

C Root

D Sibling

The root node is the only node without a parent.

What is true about a leaf node?

A It has no children

B It has no parent

C It is always the root

D It has at least one child

Leaf nodes have no children; they are at the ends of branches.

The height of a node is the number of edges from the node to:

A The root

B The deepest leaf below it

C Its parent

D Its sibling

Height counts edges down to the farthest leaf from that node.

Depth of a node is measured from:

A The leaf to the root

B The node to its leaf

C The node to its sibling

D The root to the node

Depth counts edges from the root down to the node.

If a node is at depth 3, what is its level?

A 4

B 2

C 3

D 5

Level is depth plus one, so 3 + 1 = 4.

Describe the difference between root, leaf, height, depth, and level in a tree.

Think about where the node is in the tree and how far it is from root or leaves.

Explain how you would find the height and depth of a node in a tree.

Imagine climbing up and down the tree from the node.

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