Tree Terminology Root Leaf Height Depth Level in DSA Go - 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 trees changes as the tree grows.

How does the size and shape of a tree affect how long operations take?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simple function to find the height of a binary tree
func height(node *Node) int {
  if node == nil {
    return 0
  }
  leftHeight := height(node.Left)
  rightHeight := height(node.Right)
  if leftHeight > rightHeight {
    return leftHeight + 1
  }
  return rightHeight + 1
}
    

This code finds the height of a 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: Operations grow 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.

Common Mistake

[X] Wrong: "The height function only looks at the longest path, so it runs in constant time."

[OK] Correct: Even though height depends on the longest path, the function must visit every node to be sure, so time grows with total nodes.

Interview Connect

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

Self-Check

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