Tree traversals (inorder, preorder, postorder) in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to print the root node first in a preorder traversal.

Data Structures Theory

def preorder(node):
    if node is None:
        return
    print(node.value)
    preorder(node.[1])
    preorder(node.right)

Drag options to blanks, or click blank then click option'

Aleft

Bchild

Cparent

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Calling preorder on the right child first.

Trying to access a non-existent attribute like 'parent'.

In preorder traversal, we visit the root node first, then the left subtree, followed by the right subtree. So, the first recursive call should be on the left child.

2fill in blank

medium

Complete the code to traverse the left subtree first in an inorder traversal.

Data Structures Theory

def inorder(node):
    if node is None:
        return
    inorder(node.[1])
    print(node.value)
    inorder(node.right)

Drag options to blanks, or click blank then click option'

Aparent

Bleft

Cright

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Visiting the right subtree before the left.

Printing the node value before traversing the left subtree.

In inorder traversal, we visit the left subtree first, then the root node, and finally the right subtree. So, the first recursive call should be on the left child.

3fill in blank

hard

Fix the error in the postorder traversal code to visit the right subtree last.

Data Structures Theory

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.[1])
    print(node.value)

Drag options to blanks, or click blank then click option'

Aleft

Bparent

Cright

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Printing the node value before visiting the right subtree.

Visiting the right subtree before the left.

In postorder traversal, we visit the left subtree, then the right subtree, and finally the root node. The print statement should come after both recursive calls. The blank should be filled with 'right' to visit the right subtree last.

4fill in blank

hard

Fill both blanks to complete the inorder traversal that visits left subtree, root, then right subtree.

Data Structures Theory

def inorder(node):
    if node is None:
        return
    inorder(node.[1])
    print(node.[2])
    inorder(node.right)

Drag options to blanks, or click blank then click option'

Aleft

Bvalue

Cright

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Printing the node object instead of its value.

Visiting the right child before printing the node's value.

In inorder traversal, we first visit the left child, then print the node's value, and finally visit the right child. So, the first blank is 'left' and the second blank is 'value'.

5fill in blank

hard

Fill all three blanks to complete the preorder traversal visiting root, left subtree, then right subtree.

Data Structures Theory

def preorder(node):
    if node is None:
        return
    print(node.[1])
    preorder(node.[2])
    preorder(node.[3])

Drag options to blanks, or click blank then click option'

Avalue

Bleft

Cright

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Printing the node after traversing children.

Swapping left and right child traversal order.

In preorder traversal, we print the root node's value first, then recursively traverse the left subtree, followed by the right subtree. So the blanks are 'value', 'left', and 'right' respectively.

Practice

1. Which tree traversal visits the root node first, then the left subtree, and finally the right subtree?

easy

A. Preorder traversal

B. Inorder traversal

C. Postorder traversal

D. Level order traversal

Solution

1. Step 1: Understand preorder traversal order

   Preorder traversal visits nodes in the order: root, left subtree, right subtree.

2. Step 2: Compare with other traversal types

   Inorder visits left, root, right; postorder visits left, right, root; level order visits level by level.

3. Final Answer:

   Preorder traversal -> Option A

4. Quick Check:

   Root first = Preorder [OK]

Hint: Root first means preorder traversal [OK]

Common Mistakes:

• Confusing inorder with preorder
• Thinking postorder visits root first
• Mixing level order with preorder

2. Which of the following is the correct order of nodes visited in an inorder traversal?

easy

A. Left, Right, Root

B. Root, Left, Right

C. Left, Root, Right

D. Right, Root, Left

Solution

1. Step 1: Recall inorder traversal definition

   Inorder traversal visits nodes in the order: left subtree, root, right subtree.

2. Step 2: Match with given options

   Left, Root, Right matches the left, root, right order exactly.

3. Final Answer:

   Left, Root, Right -> Option C

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Inorder always visits left subtree before root [OK]

Common Mistakes:

• Mixing preorder and inorder orders
• Assuming root is visited first in inorder
• Confusing right subtree position

3. Given the binary tree:

    A
   / \
  B   C
 /    
D   E   F

What is the postorder traversal sequence?

medium

A. D, B, E, F, C, A

B. A, B, D, E, C, F

C. B, D, E, A, C, F

D. D, E, B, F, C, A

Solution

1. Step 1: Understand postorder traversal

   Postorder visits left subtree, right subtree, then root node.

2. Step 2: Traverse given tree in postorder

   Left subtree of A: B subtree -> D, E, B; Right subtree of A: C subtree -> F, C; Finally root A.

3. Final Answer:

   D, B, E, F, C, A -> Option A

4. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Postorder ends with root node [OK]

Common Mistakes:

• Visiting root too early
• Mixing preorder and postorder
• Skipping right subtree nodes

4. A student wrote the preorder traversal of a tree as A, B, D, E, C, F but the inorder traversal as D, B, E, A, F, C. What is the error in the inorder traversal?

medium

A. The root node A is missing in inorder traversal

B. The nodes F and C are swapped in inorder traversal

C. The left subtree nodes are incorrectly ordered

D. No error, both traversals are consistent

Solution

1. Step 1: Analyze preorder traversal

   Preorder: root A, left subtree B with children D and E, right subtree C with child F.

2. Step 2: Check inorder traversal order

   Inorder should be left subtree (D, B, E), root A, right subtree (C, F). Given is D, B, E, A, F, C but F and C order is swapped.

3. Final Answer:

   The nodes F and C are swapped in inorder traversal -> Option B

4. Quick Check:

   Inorder right subtree order matters [OK]

Hint: Inorder right subtree nodes must be in correct order [OK]

Common Mistakes:

• Ignoring subtree order in inorder
• Assuming preorder and inorder can differ arbitrarily
• Missing root node in traversal

5. You have a binary tree where the inorder traversal is D, B, E, A, C, F and the preorder traversal is A, B, D, E, C, F. Which of the following postorder traversals is correct?

hard

A. F, C, D, E, B, A

B. B, D, E, F, C, A

C. D, B, E, C, F, A

D. D, E, B, F, C, A

Solution

1. Step 1: Use preorder to identify root and subtrees

   Preorder starts with A (root), then B subtree (D, E), then C subtree (F).

2. Step 2: Use inorder to confirm subtree nodes

   Inorder left subtree: D, B, E; right subtree: C, F.

3. Step 3: Construct postorder traversal

   Postorder visits left subtree (D, E, B), right subtree (F, C), then root (A).

4. Final Answer:

   D, E, B, F, C, A -> Option D

5. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Postorder ends with root after left and right subtrees [OK]

Common Mistakes:

• Mixing preorder and postorder sequences
• Swapping left and right subtree orders
• Placing root before subtrees in postorder