Tree Terminology Root Leaf Height Depth Level in DSA Javascript - Time & Space Complexity

Time Complexity: Tree Terminology Root Leaf Height Depth Level

O(n)

Understanding Time Complexity

We want to understand how the time to explore a tree changes as the tree grows.

How does the number of steps grow when we visit nodes like root, leaves, or measure height and depth?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function treeHeight(node) {
  if (!node) return -1;
  const leftHeight = treeHeight(node.left);
  const rightHeight = treeHeight(node.right);
  return Math.max(leftHeight, rightHeight) + 1;
}
    

This code finds the height of a binary tree by checking the height of left and right subtrees recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Once per node in the tree.

How Execution Grows With Input

As the tree grows, the function visits every node once to find height.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The number of steps grows directly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find height grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The height calculation only depends on the longest path, so it takes less time than visiting all nodes."

[OK] Correct: Even to find the longest path, the function must check every node to be sure no longer path exists.

Interview Connect

Understanding how tree operations scale helps you explain your approach clearly and confidently in interviews.

Self-Check

"What if we changed the tree to a linked list (all nodes have only one child)? How would the time complexity change?"

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