Height and depth of trees in Data Structures Theory - Time & Space Complexity

Time Complexity: Height and depth of trees

O(n)

Understanding Time Complexity

When working with trees, it is important to understand how the height and depth affect the time it takes to perform operations.

We want to know how the number of steps grows as the tree gets bigger.

Scenario Under Consideration

Analyze the time complexity of finding the height of a tree using recursion.

function height(node) {
  if (node == null) return -1;
  let leftHeight = height(node.left);
  let rightHeight = height(node.right);
  return 1 + Math.max(leftHeight, rightHeight);
}
    

This code calculates the height 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 to visit 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 the 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 the height grows in direct proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "The height can be found without visiting all nodes."

[OK] Correct: Because the height depends on the longest path, you must check all nodes to be sure.

Interview Connect

Understanding how tree height and depth affect time helps you explain and reason about tree operations clearly.

Self-Check

"What if the tree is balanced versus very unbalanced? How would that affect the time complexity of finding height?"