Tree Terminology Root Leaf Height Depth Level in DSA C++ - 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 work with a tree changes as the tree grows.

How does the size and shape of a tree affect the time to reach nodes like root, leaves, or calculate height and depth?

Scenario Under Consideration

Analyze the time complexity of this simple function that finds the height of a binary tree.

int height(Node* root) {
  if (root == nullptr) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}
    

This function finds the height by checking the longest path from the root to any leaf.

Identify Repeating Operations

Look for repeated work in the code.

• 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.

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

Pattern observation: The work 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 function only checks the longest path, so it runs in constant time."

[OK] Correct: Even though it finds the longest path, it must visit every node to be sure, so it takes time proportional to all nodes.

Interview Connect

Understanding how tree size affects operations like height or depth helps you explain your code clearly and shows you know how data grows in real problems.

Self-Check

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