solving a large problem by solving the same problem with a smaller scope, repeating the recursive step until the base case is reached. The case being a known answer

Backtracking is a systematic trial and error approach to finding the solution to a problem. Backtracking algorithms are useful where initially there appear to be many solutions but few survive further tests.

a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.

A queue is a collection of objects organised such that the object that has been stored in the queue the longest is the next one removed A queue is a linear data structure

A stack is a collection of objects where only the most recently inserted object can be removed at any time. A stack is a linear data structure. Last-In First-Out structure – LIFO

Linked list is a collection of objects, called nodes Every node has two components information to be stored (the data) reference to the next node (often called a link).

Extension of an ordered SLL with Additional forward links, added in a randomized way. Probabilistic data structure Based on a set of parallel linked lists

15. Describe the process of inserting a new node into a Singly Linked List

The list is empty. New node inserted as the only node The list is not empty. New node inserted somewhere within the list New node inserted at the front of the list. New node inserted at the end of the list.

16. Describe the process of inserting a new node into a SkipList

Determine level by using a probabilistic technique a random number generator to determine level of insertion. Find where to insert you will need to build an array to hold references for each level. Insert by adjusting references at each level

They use more memory than arrays because of the storage used by their pointers. Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.

Keys in the left subtree of the root precedes the key in the root Key in the root node precedes the keys in the right subtree Left and right subtrees of the root are also BSTs

proceeds along a path from the root through one child to the most distant descendant of that first child before processing the second child. Implementation uses a stack

27. Define the Breadth First Traversal of a binary tree. What data structure is used?

2n-1 where n = height, Given thatThe maximum number of nodes: in a BST of height 1 = 1 , in a BST of height 2 = 3 (The tree now has 1 node on level 0 and two nodes on level 1) in a BST of height 3 = 7

30. A binary Search Tree is created by inserting numbers in numerical order. What do you know about the shape of this tree? Explain why.

an alternative way that can be used to represent an expression with the opperators after the opperands There is only one way to represent an expression using Postfix notation. This notation is used in Complier design to generate our unambiguous code