Tree Terminology Root Leaf Height Depth Level in DSA Java - 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.

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

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 gets bigger, the function visits more nodes, so the work grows with the number of nodes.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to find the height grows in a straight line with the number of nodes.

Common Mistake

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

[OK] Correct: Even though height depends on the longest path, the function must visit every node to be sure, so it still checks all nodes.

Interview Connect

Understanding how tree operations scale helps you explain your code clearly and shows you know how data size affects performance.

Self-Check

"What if we changed the tree to be 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 concept

   The root node is the starting point of the tree and has no parent node above it.

2. Step 2: Identify the correct description

   Among the options, only the topmost node with no parent matches the root node definition.

3. Final Answer:

   The topmost node with no parent -> Option A

4. Quick Check:

   Root = topmost node with no parent [OK]

Hint: Root node has no parent, always at the top [OK]

Common Mistakes:

• Confusing root with leaf node
• Thinking root must have children
• Assuming root is any node at bottom

2. Which of the following is the correct way to declare a leaf node in Java if Node is a class representing tree nodes?

easy

A. Node leaf = new Node(); leaf.left = new Node();

B. Node leaf = null; // leaf nodes cannot be null

C. Node leaf = new Node(null, null); // no children

D. Node leaf = new Node(5); // with one child

Solution

1. Step 1: Understand leaf node definition

   A leaf node has no children, so its left and right child references should be null.

2. Step 2: Check each option for leaf node declaration

   Node leaf = new Node(5); // with one child: Node leaf = new Node(5); uses standard constructor which sets left = right = null, creating a leaf node. A adds a child. C likely causes syntax error (no such constructor). D is null, not a node.

3. Final Answer:

   Node leaf = new Node(5); // with no children -> Option D

4. Quick Check:

   Leaf node has no children = left and right null [OK]

Hint: Leaf nodes have no children, so child pointers are null [OK]

Common Mistakes:

• Assuming leaf nodes must have data only
• Creating children for leaf nodes
• Setting leaf node to null reference

3. Consider the following tree structure:

        1
       / \
      2   3
     /   / \
    4   5   6

What is the height of the tree?

medium

A. 5

B. 3

C. 2

D. 4

Solution

1. Step 1: Understand height of a tree

   Height is the number of edges on the longest path from root to a leaf node.

2. Step 2: Find longest path from root (1) to leaf

   Paths: 1->2->4 has 2 edges, 1->3->5 has 2 edges, 1->3->6 has 2 edges. So height = 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Longest path edges = 2 [OK]

Hint: Height = longest edges from root to leaf [OK]

Common Mistakes:

• Counting nodes instead of edges for height
• Confusing height with depth
• Counting root as height 1

4. Given the following code snippet, what is the error?

class Node {
  int data;
  Node left, right;
  Node(int data) {
    this.data = data;
    left = right = null;
  }
}

Node root = new Node(10);
root.left = new Node(20);
root.right = new Node(30);
root.left.left = new Node(40);
root.left.right = new Node(50);
root.right.left = new Node(60);
root.right.right = new Node(70);

System.out.println(root.left.right.data);

medium

A. NullPointerException at root.left.right

B. No error, prints 50

C. Syntax error in Node class

D. Prints 60 instead of 50

Solution

1. Step 1: Trace node assignments

   root.left.right is assigned new Node(50), so it exists and has data 50.

2. Step 2: Check print statement

   Printing root.left.right.data will print 50 without error.

3. Final Answer:

   No error, prints 50 -> Option B

4. Quick Check:

   root.left.right.data = 50 [OK]

Hint: Check if node is assigned before accessing data [OK]

Common Mistakes:

• Assuming uninitialized nodes cause error here
• Confusing left and right child nodes
• Thinking print outputs 60

5. In a tree, if the root node is at level 0, what is the depth of the node with value 6 in the tree below?

        1
       / \
      2   3
     /   / \
    4   5   6

medium

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Understand depth definition

   Depth is the number of edges from the root node to the target node.

2. Step 2: Trace path from root (1) to node 6

   Path: 1 -> 3 -> 6 has 2 edges, so depth is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Edges from root to node 6 = 2 [OK]

Hint: Depth = edges from root to node [OK]

Common Mistakes:

• Counting nodes instead of edges for depth
• Confusing depth with level starting at 1
• Assuming depth equals height