TIFR CSE 2018 | Part B | Question: 6

Question

Consider the following implementation of a binary tree data strucrure. The operator $+$ denotes list-concatenation.

That is, $[a,b,c]+[d,e]=[a,b,c,d,e].$

struct TreeNode:
 int value
 TreeNode leftChild
 TreeNode rightChild
 
function preOrder(T):
 if T == null:
  return []
 else:
  return [T.value] + preOrder(T.leftChild) + preOrder(T.rightChild)
  
function inOrder(T):
 if T == null:
  return []
 else:
  return inOrder(T.leftChild) + [T.value] + inOrder(T.rightChild)
  
function postOrder(T):
 if T == null:
  return []
 else:
  return postOrder(T.leftChild) + postOrder(T.rightChild) + [T.value] 

For some T the functions inOrder(T) and preOrder(T) return the following:

$\;\text{inOrder(T)}:\quad\; [12,10,6,9,7,2,15,5,1,13,4,3,8,14,11]$

$\text{preOrder(T)}:\quad [5,2,10,12,9,6,7,15,13,1,3,4,14,8,11]$

What does postOrder(T) return ?

• A. $[12,6,10,7,15,2,9,1,4,13,8,11,14,3,5]$
• B. $[11,8,14,4,3,1,13,15,7,6,9,12,10,2,5]$
• C. $[11,14,8,3,4,13,1,5,15,2,7,9,6,10,12]$
• D. $[12,6,7,9,10,15,2,1,4,8,11,14,3,13,5]$
• E. $\text{Cannot be uniquely determined from given information.}$

Comments

option  D?

---

@Arjun Sir, I have 1 doubt.
In order sequence is always in ASCENDING order, how come here in question the sequence changes?

---

iwasifirshad, the given tree is binary tree. So, you can’t expect ascending order. If it is binary search tree it should be in ascending order.

Answer 1

OPTION (D)

$\textbf{Post Order: 12, 6, 7, 9, 10, 15, 2, 1, 4, 8, 11, 14, 3, 13, 5}$

Answer 2

option D

Using preorder traversal we get the root of each subtree and from inorder traversal we get the left and right child repeatedly.