Data Structures

Question 1

trees

Answer 1

• data structures that consist of nodes which are linked together in a certain way
• Nodes in a tree have a parent-child relationship
• Each node is linked to 0 or more child nodes and at most 1 parent

Question 2

root

Answer 2

• special node at the top of the tree from which all other nodes descend.
• The root has no parent

Question 3

leaf

Answer 3

Nodes without any children

Question 4

binary tree

Answer 4

each node can only have 0, 1, or 2 children (at most 2 children)

Question 5

branch

Answer 5

• signifies a decision path, a choice that connects 1 node to another
• binary tree may have a left branch and a right branch

Question 6

subtree

Answer 6

mini tree within a binary tree, whose root can be any node and all of its descendants rooted at that node.

Question 7

Binary search trees(BST)

Answer 7

1. All of the nodes in the left-hand branch of a node are guaranteed to have lower values than the node itself, and
2. all of the nodes in the right-hand branch of a node are guaranteed to have a higher value than the node itself.
3. each node holds a key, a value, and left and right pointers.

Question 8

balanced tree

Answer 8

• nodes are inserted equally on the left and right branches
• the width grows exponentially with the number of nodes. This means that conversely, the height must grow logarithmically with the number of nodes. So the average case is O(log(n)).
• a skewed binary search tree is basically a linked list. Therefore, you will need to iterate through each of those nodes in order to get to the bottom of the tree to insert something. This makes the time complexity O(n).
• example of the best case would be inserting the root only, which would be O(1).

Question 9

retrieval

Answer 9

follows the same pattern as insertion. You check the value of the key against the key stored in a node in the BST and recursively follow the left or right branch accordingly.

Question 10

retrieval time complexity

Answer 10

• average time complexity of finding something in a BST would require traversing the height of a balanced tree and would be O(log(n)).
• Just like insert, the worst case for finding something in a BST will occur when the tree is skewed left or right and you are searching for the node at the bottom where everything is inserted to 1 side, so it is O(n).
• The best case is that the node you are trying to find is the root node, which would be O(1).

Question 11

removal

Answer 11

• After you find the item that you want to remove using the find process described above, there are 3 scenarios that you may encounter.
  1. no children (a leaf node)
  2. 1 child (left or right, doesn’t matter)
  3. 2 children (left and right)

Question 12

removal-with no children

Answer 12

-After you find the node, and that node has no children, you remove it from the BST by breaking the link to the parent

Question 13

removal-with 1 child

Answer 13

• you make the parent of the item you are removing point to this 1 child, and then detach the item that you want to remove from the parent. We will make 21 the right child of 19 and detach 28 from being the right child of 19.
• the child of the node that you removed (21) has a new parent (19), the parent of the node you just removed.

Question 14

removal-with 2 children

Answer 14

1. find the minimum value in the right subtree
2. replace the value of the node to be removed with the found minimum - now, the right subtree contains a duplicate
3. apply remove to the right subtree to remove the duplicate

Question 15

removal time complexity

Answer 15

you can use similar logic to insertion and retrieval to show that the best case is O(1), the average case is O(log(n)), and the worst case is O(n)

Question 16

linear search

Answer 16

you look through an array 1-by-1 until you find what you are looking for

Question 17

Binary search

Answer 17

-faster search method, which only works on sorted arrays.

-

Question 18

breadth-first search (BFS)

Answer 18

works across the rows of a tree
tree is visited level by level. In order to carry out a BFS, you need a “first-in, first-out” (FIFO) queue so you can store all the siblings in the queue and process them in the correct order.

Question 19

in-order traversal

Answer 19

in the algorithm that the left branch is visited, then the node itself is handled, then the right branch is visited

Question 20

pre-order traversal

Answer 20

If the node is handled before the branches then this is known

Question 21

post-order traversal

Answer 21

if the node is handled after the branches

Question 22

post-order traversal

Answer 22

if the node is handled after the branches

Question 23

bubble sort

Answer 23

• classic “terrible” sorting algorithm
• you keep looping through an array to find out whether adjacent values need swapping, and you keep going until there are no more values that need swapping

Question 24

Merge sort

Answer 24

• you slice the array into 2 halves and sort each half by recursively calling mergeSort. The 2 sorted halves are then merged together in the correct order using the merge
• merge the 2 lists you just keep choosing the lowest value from the left or right arrays that hasn’t already been added to the output array.
• When 1 of the arrays is empty, you add all of the remaining values from the other array to it.

Question 25

Quicksort

Answer 25

• sorting algorithm with O(nlog(n)) best and average-case performance, although it is O(n^2) in the worst case
• quicksort is more commonly used than merge sort, as it is more cache-efficient and can easily be performed in place
• partition the array into 2 halves around a pivot value. All of the values which are less than the pivot value go to 1 half of the array, and all of the values which are greater than the pivot go to the other half of the array. You then recursively sort the 2 halves of the array until the halves are of length 0 or 1.

Question 26

partitioning algorithms

Answer 26

common in-place algorithm is Lomuto’s algorithm