edited by
1,356 views
4 votes
4 votes

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 ?

  1. $[12,6,10,7,15,2,9,1,4,13,8,11,14,3,5]$
  2. $[11,8,14,4,3,1,13,15,7,6,9,12,10,2,5]$
  3. $[11,14,8,3,4,13,1,5,15,2,7,9,6,10,12]$
  4. $[12,6,7,9,10,15,2,1,4,8,11,14,3,13,5]$
  5. $\text{Cannot be uniquely determined from given information.}$
edited by

2 Answers

Best answer
5 votes
5 votes

OPTION (D)

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

edited by
Answer:

Related questions

16 votes
16 votes
6 answers
1
Arjun asked Dec 10, 2017
3,323 views
What is the minimum number of students needed in a class to guarantee that there are at least $6$ students whose birthdays fall in the same month ?$6$$23$$61$$72$$91$
4 votes
4 votes
1 answer
2