DSA Series Chapter 11 : Tree Traversal – Order of Nodes

on

 

[Follow here] for daily coding insights.

DSA Series Chapter 11 : 

Tree Traversal – Order of Nodes

Traversal refers to the systematic process of visiting every node in a tree exactly once. There are two major traversal categories:

  1. Depth-First Traversals (DFT)

  2. Breadth-First Traversal (BFT)

1. Depth-First Traversals (DFT)

Depth-first traversal explores nodes as far as possible along each branch before backtracking. It has three classical orders depending on the position of the root node in the traversal sequence.

A. Inorder Traversal (Left, Root, Right)

  • Visit left subtree

  • Visit root

  • Visit right subtree

Sequence: L → R → R

Applicability:

  • Mainly defined for Binary Trees.

  • In Binary Search Trees, inorder traversal prints the data in sorted order.

B. Preorder Traversal (Root, Left, Right)

  • Visit root

  • Visit left subtree

  • Visit right subtree

Sequence: R → L → R

Applicability:

  • Used to create a copy of the tree.

  • Used to serialize/deserialize tree structures.

Algorithms : PREORDER(node)

PREORDER(node):
    if node == NULL:
        return

    visit(node)            // Step 1: Process root
    PREORDER(node.left)    // Step 2: Traverse left subtree
    PREORDER(node.right)   // Step 3: Traverse right subtree

C. Postorder Traversal (Left, Right, Root)

  • Visit left subtree

  • Visit right subtree

  • Visit root

Sequence: L → R → R

Applicability:

  • Used to delete/free nodes in memory safely.

  • Used in evaluating expression trees (operands first, operators later).

Algorithm: POSTORDER(node)

POSTORDER(node):
    if node == NULL:
        return

    POSTORDER(node.left)    // Step 1: Traverse left subtree
    POSTORDER(node.right)   // Step 2: Traverse right subtree
    visit(node)

2. Breadth-First Traversal (Level-Order Traversal)

Level Order Traversal (LOT)

  • Visit nodes level by level from top to bottom.

  • Uses a queue for implementation.

Order Example:
Level 0 → Level 1 → Level 2 → Level 3 → …

Applicability:

  • Used in shortest path calculations (when edges have equal weights).

  • Used in applications like finding height, printing tree level-wise, etc.


Algorithm : LEVEL_ORDER(root)
LEVEL_ORDER(root):
    if root == NULL:
        return

    create an empty queue Q
    enqueue(Q, root)

    while Q is not empty:
        node = dequeue(Q)
        visit(node)

        if node.left != NULL:
            enqueue(Q, node.left)

        if node.right != NULL:
            enqueue(Q, node.right)

Illustrative Example

Consider the tree:

        A
       / \
      B   C
     / \   \
    D   E   F

The traversal outputs will be:

Traversal Type Output Sequence
Inorder D, B, E, A, C, F
Preorder A, B, D, E, C, F
Postorder D, E, B, F, C, A
Level Order A, B, C, D, E, F

Below are Tree Traversal Exercises with Complete Solutions, designed for engineering professional students following your DSA roadmap.

The exercises cover Preorder, Postorder, Inorder, and Level-Order logically but focus mainly on Preorder, Postorder, Level-Order as per your previous topic request.

TREE TRAVERSAL EXERCISES

(With Solutions at the End)

SECTION A – BASIC TO INTERMEDIATE QUESTIONS

Q1.

Given the following binary tree, write the Preorder, Postorder, and Level-Order traversals.

        A
       / \
      B   C
     / \
    D   E

Q2.

Construct a binary tree from the following connections and write the Preorder traversal:

  • Root = 10

  • 10 → left = 5

  • 10 → right = 20

  • 5 → left = 3

  • 5 → right = 8

Q3.

For the tree below, list the nodes in Postorder.

        1
       / \
      2   3
         / \
        4   5

Q4.

Perform Level-Order traversal on this tree:

        K
       / \
      L   M
         / \
        N   O

Q5.

A binary tree contains only the nodes:
7, 4, 9, 2, 5 (Not a BST — random structure)

The structure is:

      7
     / \
    4   9
   /
  2
   \
    5

Find Preorder and Postorder.

SECTION B – HIGHER-LEVEL QUESTIONS

Q6.

A full binary tree is constructed as follows:

            X
         /     \
        A       B
       / \     / \
      C   D   E   F

Find:

  1. Preorder

  2. Inorder

  3. Postorder

  4. Level-order

Q7.

Consider this tree:

            50
           /  \
         30    70
        / \    /
      20  40  60

Write the Postorder traversal and explain the visiting pattern (Left → Right → Root).

Q8.

Given the binary tree below, find the sequence printed by Level Order Traversal:

             R
           /   \
          P     Q
         / \     \
        L   M     T

Q9.

For the following tree:

      11
     /  \
    7    15
         / \
        13  18

Write Preorder and Postorder traversals.

Q10.

Define a tree such that:

  • Preorder traversal gives: A, B, D, E, C, F

  • Inorder traversal gives: D, B, E, A, F, C

Draw the tree and verify the Postorder traversal.

SOLUTIONS SECTION

Solution 1

Tree:

    A
   / \
  B   C
 / \
D   E

  • Preorder: A, B, D, E, C

  • Postorder: D, E, B, C, A

  • Level Order: A, B, C, D, E

Solution 2

Tree:

       10
      /  \
     5    20
    / \
   3   8

Preorder: 10, 5, 3, 8, 20

Solution 3

Tree:

    1
   / \
  2   3
     / \
    4   5

Postorder (L → R → Root):
2, 4, 5, 3, 1

Solution 4

Tree:

    K
   / \
  L   M
     / \
    N   O

Level Order: K, L, M, N, O

Solution 5

Tree:

      7
     / \
    4   9
   /
  2
   \
    5

  • Preorder: 7, 4, 2, 5, 9

  • Postorder: 5, 2, 4, 9, 7

Solution 6

Tree:

          X
       /     \
      A       B
     / \     / \
    C   D   E   F

  1. Preorder: X, A, C, D, B, E, F

  2. Inorder: C, A, D, X, E, B, F

  3. Postorder: C, D, A, E, F, B, X

  4. Level-order: X, A, B, C, D, E, F

Solution 7

Tree:

        50
       /  \
     30    70
    / \    /
  20  40  60

Postorder is:

20, 40, 30, 60, 70, 50

Visiting Pattern Explanation

  • Visit entire left subtree (20, then 40, then 30).

  • Visit entire right subtree (60, then 70).

  • Visit root (50).

Solution 8

Tree:

        R
      /   \
     P     Q
    / \     \
   L   M     T

Level Order:
R, P, Q, L, M, T

Solution 9

Tree:

      11
     /  \
    7    15
         / \
        13  18

  • Preorder: 11, 7, 15, 13, 18

  • Postorder: 7, 13, 18, 15, 11

Solution 10

Given:
Preorder: A, B, D, E, C, F
Inorder: D, B, E, A, F, C

Reconstructed Tree:

        A
       / \
      B   C
     / \   \
    D   E   F

Postorder: D, E, B, F, C, A


TREE TRAVERSAL EXERCISES (UNSOLVED)

SECTION A – BASIC LEVEL

Q1.

For the following tree, write Preorder, Postorder, and Level Order traversals:

        A
       / \
      B   C
     / \
    D   E

Q2.

Construct the tree from the connections below and write the Preorder traversal:

  • Root: 12

  • 12 → left = 7

  • 12 → right = 25

  • 7 → left = 3

  • 7 → right = 9

Q3.

For the tree below, write the Postorder traversal:

        P
       / \
      Q   R
         / \
        S   T

Q4.

Perform Level-Order traversal for this tree:

        X
       / \
      Y   Z
         / \
        M   N

Q5.

Given this binary tree:

        8
       / \
      3   10
     / \
    1   6

Write Preorder and Postorder traversals.

SECTION B – INTERMEDIATE LEVEL

Q6.

For the tree:

        4
      /   \
     2     7
    / \     \
   1   3     9

Write the Inorder, Preorder, and Postorder traversals.

Q7.

A binary tree is defined as follows:

           15
          /  \
        10    20
       / \    /
      5  12  18

Write the Postorder traversal.

Q8.

Perform Level-Order traversal:

           A
         /   \
        B     C
         \   / \
          D E   F

Q9.

For this tree:

        25
       /  \
      15   40
     / \    \
    10 20    50

Write Preorder and Inorder traversals.

Q10.

A tree has the following structure:

           K
         /   \
        L     M
       / \     \
      N   O     P

Write Postorder and Level-order traversals.

SECTION C – ADVANCED LEVEL

Q11.

Given:

  • Preorder: A, B, D, E, C, F, G

  • Inorder: D, B, E, A, F, C, G

Reconstruct the tree and write the Postorder traversal.

Q12.

Consider this binary tree:

           1
         /   \
        2     3
       / \   / \
      4  5  6   7
           \
            8

Write all four traversals:

  • Preorder

  • Inorder

  • Postorder

  • Level-Order

Q13.

A complete binary tree is given:

                H
           /         \
          I           J
        /   \       /   \
       K     L     M     N
            /
           O

Write Level-Order, Preorder, and Postorder.

Q14.

Given this general binary tree:

        90
       /  \
     50    120
      \      \
      60     150
            /
          130

Write Inorder, Preorder, and Level-order traversals.

Q15.

For the binary tree below:

          T
        /   \
       R     W
      /     / \
     Q     V   X
      \       /
       S     Y

Write Preorder, Postorder, and Level-order.


ALSO CHECK 

DS(Data Structure) Python&C Edition

DSA Series Chapter 1 Time & Space Complexity ( C Edition)

DSA Series Chapter 2 Arrays  (C Version)


DSA Series Chapter 2 Arrays  (Python Version)

DSA Series Chapter 3 Strings (C Version)


DSA Series Chapter 3 Strings (Python Version)


DSA Series Chapter 4 Linked Lists (Python Version)


DSA Series Chapter 4 Linked Lists (C Version)


DSA Series Chapter 5 Stacks (Python Version)


DSA Series Chapter 5  Stacks  (C Version)























Tail Recursion Optimization: How Compilers Convert Recursion Into Iteration


Advanced Recursion: Memoization vs. Tabulation — The Deep Optimization Blueprint for Professionals


Advanced Sorting Algorithms: Merge Sort Internals — Merge Tree, Cache Behavior & Real Cost Analysis


Enjoyed this post? [Follow here] for daily coding insights.

Comments

Post a Comment