Tree Traversal Preorder Root Left Right in DSA Java - Time & Space Complexity

Time Complexity: Tree Traversal Preorder Root Left Right

O(n)

Understanding Time Complexity

We want to understand how the time needed to visit all nodes in a tree grows as the tree gets bigger.

How does the number of steps change when we do a preorder traversal (root, then left, then right)?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void preorderTraversal(TreeNode node) {
    if (node == null) return;
    System.out.println(node.val); // Visit root
    preorderTraversal(node.left);  // Traverse left subtree
    preorderTraversal(node.right); // Traverse right subtree
}
    

This code visits each node in the tree starting from the root, then left child, then right child recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node once (printing its value).
• How many times: Exactly once per node in the tree.

How Execution Grows With Input

Each node is visited once, so the total steps grow directly 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 linearly as the tree size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the traversal grows directly in proportion to the number of nodes.

Common Mistake

[X] Wrong: "Preorder traversal takes more time because it visits the root first and then both subtrees separately."

[OK] Correct: Each node is visited exactly once regardless of order, so the total time depends only on the number of nodes, not the order.

Interview Connect

Understanding preorder traversal time helps you explain how tree algorithms scale, a key skill in many coding challenges and interviews.

Self-Check

"What if we changed preorder traversal to inorder traversal? How would the time complexity change?"

Practice

1. What is the order of nodes visited in a preorder tree traversal?

easy

A. Left, Root, Right

B. Right, Root, Left

C. Left, Right, Root

D. Root, Left, Right

Solution

1. Step 1: Understand preorder traversal definition

   Preorder traversal visits the root node first, then the left subtree, and finally the right subtree.

2. Step 2: Match the order with options

   Root, Left, Right matches the order Root, Left, Right exactly.

3. Final Answer:

   Root, Left, Right -> Option D

4. Quick Check:

   Preorder = Root, Left, Right [OK]

Hint: Remember preorder starts with the root node first [OK]

Common Mistakes:

• Confusing preorder with inorder or postorder
• Visiting left before root
• Visiting right before left

2. Which of the following Java method signatures correctly represents a preorder traversal method for a binary tree node class named Node?

easy

A. void preorderTraversal(Node root) {}

B. int preorderTraversal(Node root) {}

C. Node preorderTraversal() {}

D. void preorderTraversal() {}

Solution

1. Step 1: Identify correct method signature for preorder traversal

   Preorder traversal usually returns void and takes the root node as input to traverse the tree.

2. Step 2: Check options for matching signature

   void preorderTraversal(Node root) {} matches void return type and takes Node root as parameter, which is correct.

3. Final Answer:

   void preorderTraversal(Node root) {} -> Option A

4. Quick Check:

   Traversal method is void and takes root node [OK]

Hint: Traversal methods usually return void and take root node [OK]

Common Mistakes:

• Using return type int instead of void
• Not passing root node as parameter
• Returning Node instead of void

3. Given the following binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of a preorder traversal?

medium

A. [2, 4, 5, 1, 3]

B. [4, 2, 5, 1, 3]

C. [1, 2, 4, 5, 3]

D. [1, 3, 2, 4, 5]

Solution

1. Step 1: Start preorder traversal at root node 1

   Visit 1 first, then move to left subtree.

2. Step 2: Traverse left subtree of 1: nodes 2, 4, 5

   Visit 2, then 4 (left child), then 5 (right child).

3. Step 3: Traverse right subtree of 1: node 3

   Visit 3 last.

4. Final Answer:

   [1, 2, 4, 5, 3] -> Option C

5. Quick Check:

   Preorder = Root, Left, Right = [1, 2, 4, 5, 3] [OK]

Hint: Follow Root, then left subtree, then right subtree order [OK]

Common Mistakes:

• Mixing preorder with inorder or postorder
• Visiting right subtree before left
• Skipping leaf nodes

4. Consider this Java preorder traversal method for a binary tree node class Node:

void preorder(Node root) {
  if (root == null) return;
  preorder(root.left);
  System.out.print(root.data + " ");
  preorder(root.right);
}

What is the error in this code?

medium

A. It prints nodes in inorder, not preorder

B. It causes a NullPointerException

C. It misses the right subtree

D. It prints nodes in postorder

Solution

1. Step 1: Analyze the order of operations in the method

   The method first recursively visits left subtree, then prints root data, then visits right subtree.

2. Step 2: Compare with preorder definition

   Preorder should print root first, but this code prints root after left subtree, which is inorder traversal.

3. Final Answer:

   It prints nodes in inorder, not preorder -> Option A

4. Quick Check:

   Print before left recursion for preorder [OK]

Hint: Print root before recursive calls for preorder [OK]

Common Mistakes:

• Printing after left subtree instead of before
• Confusing preorder with inorder
• Missing base case for null

5. You want to collect all node values of a binary tree in preorder traversal into a list in Java. Which code snippet correctly does this?

hard

A. void preorder(Node root, List<Integer> list) {
if (root == null) return;
preorder(root.left, list);
list.add(root.data);
preorder(root.right, list);
}

B. void preorder(Node root, List<Integer> list) {
if (root == null) return;
list.add(root.data);
preorder(root.left, list);
preorder(root.right, list);
}

C. void preorder(Node root, List<Integer> list) {
if (root == null) return;
preorder(root.left, list);
preorder(root.right, list);
list.add(root.data);
}

D. void preorder(Node root, List<Integer> list) {
if (root == null) return;
preorder(root.right, list);
list.add(root.data);
preorder(root.left, list);
}

Solution

1. Step 1: Understand preorder traversal order

   Preorder visits root first, then left subtree, then right subtree.

2. Step 2: Check which code adds root data before recursive calls

   void preorder(Node root, List<Integer> list) { if (root == null) return; list.add(root.data); preorder(root.left, list); preorder(root.right, list); } adds root.data to list first, then recursively visits left and right subtrees, matching preorder.

3. Final Answer:

   void preorder(Node root, List<Integer> list) { if (root == null) return; list.add(root.data); preorder(root.left, list); preorder(root.right, list); } -> Option B

4. Quick Check:

   Add root before left and right recursion [OK]

Hint: Add root data before recursive calls for preorder list [OK]

Common Mistakes:

• Adding node data after left subtree (inorder)
• Adding node data after both subtrees (postorder)
• Visiting right subtree before left