Tree Terminology Root Leaf Height Depth Level in DSA Typescript

Mental Model

A tree is a set of connected points where one is the start (root), some have no children (leaves), and each point has a position measured by height, depth, and level.

Analogy: Think of a family tree: the oldest ancestor is the root, youngest family members with no children are leaves, height is how far the longest branch goes down, depth is how far a person is from the ancestor, and level groups people by generation.

      Root (A)
       /    \
     B       C
    / \       \
   D   E       F

Legend:
- Root: A
- Leaves: D, E, F
- Height of tree: 2 (longest path from A to D or F)
- Depth of node E: 2 (steps from A to E)
- Level 0: A
- Level 1: B, C
- Level 2: D, E, F

Dry Run Walkthrough

Input: Tree with nodes: A is root; A has children B and C; B has children D and E; C has child F

Goal: Understand and identify root, leaves, height, depth, and level in the tree

Step 1: Identify the root node

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

Why: Root is the starting point of the tree with no parent

Step 2: Find leaf nodes (nodes with no children)

Leaves: D, E, F

Why: Leaves are endpoints with no children

Step 3: Calculate depth of node E

Depth of E: 2 (A -> B -> E)

Why: Depth is steps from root to the node

Step 4: Calculate height of node B

Height of B: 1 (longest path B -> D or B -> E)

Why: Height is longest path from node down to a leaf

Step 5: Assign levels to nodes

Level 0: A
Level 1: B, C
Level 2: D, E, F

Why: Level groups nodes by their depth

Result:

Root: A
Leaves: D, E, F
Height of tree: 2
Depth of E: 2
Levels: 0: A, 1: B,C, 2: D,E,F

Annotated Code

DSA Typescript

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

function findRoot(nodes: TreeNode[]): TreeNode | null {
  // Root has no parent, so find node not in any children list
  const allNodes = new Set(nodes);
  const childNodes = new Set<TreeNode>();
  for (const node of nodes) {
    for (const child of node.children) {
      childNodes.add(child);
    }
  }
  for (const node of allNodes) {
    if (!childNodes.has(node)) return node;
  }
  return null;
}

function findLeaves(root: TreeNode): TreeNode[] {
  // Leaves have no children
  const leaves: TreeNode[] = [];
  function dfs(node: TreeNode) {
    if (node.children.length === 0) {
      leaves.push(node);
    } else {
      for (const child of node.children) dfs(child);
    }
  }
  dfs(root);
  return leaves;
}

function nodeDepth(root: TreeNode, target: TreeNode, depth = 0): number {
  if (root === target) return depth;
  for (const child of root.children) {
    const d = nodeDepth(child, target, depth + 1);
    if (d !== -1) return d;
  }
  return -1;
}

function nodeHeight(node: TreeNode): number {
  if (node.children.length === 0) return 0;
  let maxHeight = 0;
  for (const child of node.children) {
    const h = nodeHeight(child);
    if (h > maxHeight) maxHeight = h;
  }
  return maxHeight + 1;
}

function assignLevels(root: TreeNode): Map<number, string[]> {
  const levels = new Map<number, string[]>();
  function dfs(node: TreeNode, level: number) {
    if (!levels.has(level)) levels.set(level, []);
    levels.get(level)!.push(node.value);
    for (const child of node.children) dfs(child, level + 1);
  }
  dfs(root, 0);
  return levels;
}

// 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);

const nodes = [A, B, C, D, E, F];
const root = findRoot(nodes);
const leaves = root ? findLeaves(root) : [];
const depthE = root ? nodeDepth(root, E) : -1;
const heightTree = root ? nodeHeight(root) : -1;
const levels = root ? assignLevels(root) : new Map();

console.log(`Root: ${root?.value}`);
console.log(`Leaves: ${leaves.map(n => n.value).join(', ')}`);
console.log(`Height of tree: ${heightTree}`);
console.log(`Depth of E: ${depthE}`);
console.log('Levels:');
for (const [level, vals] of levels.entries()) {
  console.log(`Level ${level}: ${vals.join(', ')}`);
}

for (const node of allNodes) { if (!childNodes.has(node)) return node; }

Identify root as node not found in any children list

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

Collect nodes with no children as leaves

if (root === target) return depth;

Return depth when target node is found

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

Height of leaf node is zero

levels.get(level)!.push(node.value);

Group nodes by their level during traversal

Output

Root: A

Leaves: D, E, F

Height of tree: 2

Depth of E: 2

Levels:

Level 0: A

Level 1: B, C

Level 2: D, E, F

Complexity Analysis

Time: O(n) because each node is visited once in traversals

Space: O(n) for storing nodes, recursion stack, and levels map

vs Alternative: Compared to repeated searches, this single traversal approach is efficient and avoids redundant work

Edge Cases

Empty tree (no nodes)

Root is null, leaves empty, depth and height -1

DSA Typescript

if (!root) return null or empty results

Single node tree

Root and leaf are the same node, height and depth zero

DSA Typescript

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

Node not found when calculating depth

Returns -1 indicating node absent

DSA Typescript

return -1 when target not found in subtree

When to Use This Pattern

When a problem involves hierarchical data or family-like relationships, recognize tree terminology to understand node roles and positions.

Common Mistakes

Mistake: Confusing height and depth definitions
Fix: Remember depth counts steps from root down; height counts steps from node down to leaf

Mistake: Assuming root is always first node in list
Fix: Find root by checking which node is not anyone's child

Summary

Defines key parts of a tree: root, leaves, height, depth, and level.

Use when you need to understand or explain positions and roles of nodes in a tree.

The root starts the tree, leaves end branches, depth measures distance from root, height measures distance to leaves, and level groups nodes by depth.