PadhaikoAll subjects

Past exam question: 2078 Poush (Back), Q6(b)

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

Topic: Definition and tree terminologies · Binary trees · Binary search tree

Question

Briefly explain pre-order, in-order, post-order tree traversal methods with example.

Solution

Three Depth-First Binary Tree Traversal Orders:

  1. Pre-order (Root -> Left -> Right): Visit the root first, then recursively traverse the left subtree, then the right subtree. Used to clone a tree or produce prefix expressions.
  2. In-order (Left -> Root -> Right): Traverse left subtree, visit root, then traverse right subtree. Produces sorted output on a Binary Search Tree.
  3. Post-order (Left -> Right -> Root): Traverse left subtree, traverse right subtree, then visit root last. Used to free/delete nodes bottom-up or produce postfix expressions.

Example on a Small Binary Tree:

      +
     / \
    A   B
Answer:

All past exam questions for Data Structure and Algorithms