Question

Question 2 (10 marks) Linked Data Structures: Answer both parts below. Part A (5 marks): The in-order traversal of a binary tree processes the nodes in the order ABCD. The post-order traversal of the same binary tree processes the nodes in the order ACDB. Draw the tree below. Part B (5 marks) Inserting one element at a time, what is the best case time complexity to add n elements to an initially empty linked list so that the stored values will be sorted from smallest to largest? Explain. A BST has n nodes. What is the time complexity of an in-order traversal?

Answer 1

$\color{blue}\underline{Part\;A:}$

A V

Part B

To insert one value to sorted list of n elements, first we have to find the position to insert new element.
For that we have to loop through all the values in the linked list.

So, we can say that, to insert one value to sorted list of n elements is O(n)

So, To insert n elements time complexity = n*n = 
O(n2)

===================

Time complexity of an in-order traversal of BST is O(n)