CODEWITHSUNDEEP
binary-treetraversal
user6027133
user6027133

Reputation: 23

Data Structures: Binary tree traversal

Hi I'm a bit confused with this tree and need help in figuring out if I'm choosing the right answer.

Tree :

  A
 / \
B   C
   / \
  D   E

Lets do the traversal first:

  1. In-order : BADCE
  2. Pre-Order : ABCDE
  3. Post-Order : BDECA

Questions:

  1. Which of the following traversals yields BADEC?

a. only in-order b. only level order c. only post-order d. only pre-order e. pre-order and level order f. in-order and level order g. none of the above

Answer g

Which of the following is a post-order traversal of the BST? a. ACEDB b. ABDCE c. BDECA d. EDCBA e. BADCE f. BADEC g. one of the above

Answer g

Can someone please confirm if I have done the traversal correctly and have chosen the correct answer for both question.

Thanks

Upvotes: 1

Views: 1052

Answers (1)

Joy Sun
Joy Sun

Reputation: 25

The three traversal algorithms is a recursive algorithm. This means that in order to traverse the entire tree rooted at node A, the algorithm will split and finish the task in three parts:

  1. traverse the subtree rooted at B (A's left child)
  2. traverse the subtree rooted rooted at C (A's right child)
  3. traverse/visit A itself

The order of the three tasks depends on which order you use: - In-order (Left, Root, Right) does task1, task3, and then task2. - Pre-order (Root, Left, Right) does task3, task1, and then task2. - Post-order (Left, Right, Root) does task1, task2, and then task3

Continue the recursive algorithm: to traverse the subtree rooted at B, it will split the task further and traverse the subtree rooted at B's left child, the subtree rooted at B's right child, and then B.

The "splitting task" continues until the subtree to traverse contains only one root node. In this case, the algorithm visits the root node and returns to the remaining sub-tasks. Same thing happens to the subtree rooted at C, A's right child.

Here are the detailed steps to traverse the tree in the question in 3 different orders and to answer the questions using the traversal results:

  1. In-order traversal (Left, Root, Right):
    • traverse subtree rooted at B
      • visit B
    • visit A
    • traverse subtree rooted at C
      • traverse C's left subtree
        • visit D
      • visit C
      • traverse C's right subtree
        • visit E

In-order: BADCE

  1. Pre-order traversal (Root, Left, Right)
    • visit A
    • traverse subtree rooted at B
      • visit B
    • traverse subtree rooted at C
      • visit C
      • traverse C's left subtree
        • visit D
      • traverse C's right subtree
        • visit E

Pre-order: ABCDE

  1. Post-order traversal (Left, Right, Root)
    • traverse subtree rooted at B
      • visit B
    • traverse subtree rooted at C
      • traverse C's left subtree
        • visit D
      • traverse C's right subtree
        • visit E
      • visit C
    • visit A

Post-order: BDECA

You can check if your traversal results are the same as above.

Looking at the traversal results, we know that the answer to your question 1 is g, and the answer to your question 2 is c.

Upvotes: 2

Related Questions