Programming: Sorted Linked List, Binary Tree Traversal, and Efficient Sorting Algorithms

Running head: PROGRAMMING
Programming
Name of the Student
Name of the University
Author Note:

1PROGRAMMING
Table of Contents
Answer to Question 1..........................................................................................................2
Part A...............................................................................................................................2
Part B...............................................................................................................................2
Answer to Question 2..........................................................................................................3
References............................................................................................................................4

2PROGRAMMING
Answer to Question 1
Part A
Ans:
Insertion of new element in the sorted linked list requires updating the head pointer
newnode->next = head;
head = newnode;
Insertion at the tail requires to place a pointer on the tail element so that element can be
easily added and updated at the tail pointer
tail->next = newnode;
tail = newnode;
Insertion of new element in the sorted link list requires O (1) time if all the place of
insertion is already known. Considering the sorted linked list, the element can be inserted
without proper acknowledgement where the inserted element will go. It will take O (n) times if
search is to carried on the whole list for finding where the elements goes.
Part B
The in-order traversal of a binary tree processes the nodes in the order
ATAA. The post-order traversal of the same binary tree processes the nodes in the order
AATA. The final tree is given below: