Tree Traversal Preorder Root Left Right in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the order of visiting nodes in Preorder Tree Traversal?

In Preorder traversal, nodes are visited in this order: Root first, then Left subtree, and finally Right subtree.

intermediate

Why is Preorder traversal useful?

Preorder traversal is useful for copying a tree or getting a prefix expression of an expression tree because it visits the root before its children.

beginner

Given a binary tree, what is the first node visited in Preorder traversal?

The first node visited is always the root node of the tree.

beginner

What is the Preorder traversal output for this tree?

    1
   / \
  2   3
 / \
4   5

The Preorder traversal visits nodes as: 1 (root), 2 (left child), 4 (left of 2), 5 (right of 2), 3 (right child). So output is: 1 -> 2 -> 4 -> 5 -> 3

intermediate

What is the main difference between Preorder and Inorder traversal?

Preorder visits the root before its children (Root, Left, Right), while Inorder visits the left subtree first, then root, then right subtree (Left, Root, Right).

In Preorder traversal, which node is visited first?

A Right child

B Left child

C Root node

D Leaf node

Preorder traversal always visits the root node first before its children.

What is the correct Preorder traversal sequence for this tree?

  10
 /  \
5    15

A 10 -> 5 -> 15

B 5 -> 10 -> 15

C 5 -> 15 -> 10

D 15 -> 10 -> 5

Preorder visits root first (10), then left child (5), then right child (15).

Which of these is NOT a step in Preorder traversal?

A Visit root

B Traverse left subtree

C Traverse right subtree

D Traverse right subtree before left subtree

Preorder traversal visits left subtree before right subtree.

Preorder traversal is especially useful for:

A Getting postfix expressions

B Copying a tree

C Sorting elements

D Finding minimum value

Preorder traversal visits root first, which helps in copying the tree structure.

If a tree has only one node, what is the Preorder traversal output?

A That single node

B Empty

C Null

D Depends on the tree

With one node, Preorder traversal visits that node first and only.

Explain the steps of Preorder traversal on a binary tree.

Think about the order Root, Left, Right.

Describe a real-life example where Preorder traversal could be useful.

Consider when you need to process a parent before its children.

Practice

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

easy

A. Right, Root, Left

B. Left, Root, Right

C. Root, Left, Right

D. Left, Right, Root

Solution

1. Step 1: Understand preorder traversal definition

   Preorder traversal means visiting 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 as defined.

3. Final Answer:

   Root, Left, Right -> Option C

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 subtree before root
• Mixing up left and right subtree order

2. Which of the following is the correct Python function header for a preorder traversal of a binary tree node named root?

easy

A. def preorder(root):

B. def preorder_traversal():

C. def preorder(root, left, right):

D. def preorder(root, node):

Solution

1. Step 1: Identify function parameters for preorder traversal

   The function needs the root node to start traversal, so it should accept one parameter named root.

2. Step 2: Check options for correct syntax

   def preorder(root): defines a function with one parameter root, which is correct and simple for preorder traversal.

3. Final Answer:

   def preorder(root): -> Option A

4. Quick Check:

   Function header with root parameter [OK]

Hint: Preorder function usually takes only the root node [OK]

Common Mistakes:

• Adding unnecessary parameters
• Missing the root parameter
• Incorrect function syntax

3. Given the binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of the preorder traversal?

medium

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

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

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

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

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

   Visit 2, then its left child 4, then right child 5.

3. Step 3: Traverse right subtree of 1

   Visit 3 last.

4. Final Answer:

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

5. Quick Check:

   Preorder visits root, left, right = [1, 2, 4, 5, 3] [OK]

Hint: Visit root first, then left subtree, then right subtree [OK]

Common Mistakes:

• Visiting left subtree before root
• Swapping left and right children
• Confusing preorder with inorder or postorder

4. Consider this preorder traversal function:

def preorder(root):
    if root is None:
        return
    print(root.val)
    preorder(root.right)
    preorder(root.left)

What is the error in this code?

medium

A. It misses printing the root node

B. It does not check if root is None

C. It prints node values twice

D. It visits right subtree before left subtree, reversing preorder order

Solution

1. Step 1: Analyze the order of recursive calls

   The function calls preorder on root.right before root.left, which reverses the expected left-right order.

2. Step 2: Understand preorder traversal order

   Preorder must visit root, then left subtree, then right subtree. This code visits right subtree before left subtree, which is incorrect.

3. Final Answer:

   It visits right subtree before left subtree, reversing preorder order -> Option D

4. Quick Check:

   Left subtree must come before right in preorder [OK]

Hint: Left subtree must be visited before right in preorder [OK]

Common Mistakes:

• Swapping left and right recursive calls
• Forgetting base case check
• Printing nodes multiple times

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

hard

A. def preorder(root):
if root is None:
return []
return [root.val] + preorder(root.left) + preorder(root.right)

B. def preorder(root):
result = []
if root:
preorder(root.left)
result.append(root.val)
preorder(root.right)
return result

C. def preorder(root):
result = []
if root:
result.append(root.val)
result.extend(preorder(root.left))
result.extend(preorder(root.right))
return result

D. def preorder(root):
if root is None:
return []
return preorder(root.left) + [root.val] + preorder(root.right)

Solution

1. Step 1: Understand preorder traversal collection

   Preorder visits root first, then left subtree, then right subtree. We must collect values in this order.

2. Step 2: Analyze each option's return order

   def preorder(root): if root is None: return [] return [root.val] + preorder(root.left) + preorder(root.right) returns [root.val] + preorder(left) + preorder(right), which matches preorder order correctly.

3. Step 3: Identify errors in other options

   def preorder(root): result = [] if root: result.append(root.val) result.extend(preorder(root.left)) result.extend(preorder(root.right)) return result uses result list but calls preorder recursively without passing result, causing empty lists. def preorder(root): result = [] if root: preorder(root.left) result.append(root.val) preorder(root.right) return result appends root after left subtree, which is inorder. def preorder(root): if root is None: return [] return preorder(root.left) + [root.val] + preorder(root.right) places root.val between left and right, which is inorder.

4. Final Answer:

   def preorder(root): if root is None: return [] return [root.val] + preorder(root.left) + preorder(root.right) -> Option A

5. Quick Check:

   Preorder = root + left + right [OK]

Hint: Return root value first, then left and right lists concatenated [OK]

Common Mistakes:

• Appending root after left subtree (inorder)
• Not returning combined list properly
• Using mutable list without passing it recursively