CS50 Data Structures

Question 1

Arrays (insertion, deletion, lookup, sort, size)

Answer 1

Insertion is bad - costs of shifting to fit an element in the middle
deletion is bad - lost of shifting after removing an element
lookup is great - random access, constant time
relatively easy to sort
relatively small size-wise
stuck with a fixed size, no flexibility

Question 2

Linked Lists (insertion, deletion, lookup, sort, size)

Answer 2

Insertion is easy - just tack onto the front
deletion is easy - once you find the element
lookup is bad - have to rely on linear search
relatively difficult to sort - unless you’re willing to compromise on super-fast insertion and instead sort as you construct
relatively small size-wise (not as small as arrays)

Question 3

What is depth first? What is the difference between depth first preorder, inorder, and post order?

Answer 3

Search all the nodes down one side of the tree before going to the other side

preorder
-root, left, right

inorder
-left,root,right

postorder
-left,right,root

Question 4

What is breath first search?

Answer 4

visit every node at the current level

Question 5

How do you reverse a linked list

Answer 5

• set a newHead and a newTail
• the newTail is instantiated and will always be the original head
• the newHead is instantiated as the next of head
• the newHead will be the next of the newTail at the end of each loop iteration
• loop through the nodes
• set a temp variable to the .next of the newHead
• point newHead to the head
• point newTail (the original head) to temp
• set head to newHead
• set newHead to temp
• return head

var reverseList = function(head) {
    if(!head || !head.next) return head

    let newTail = head
    let newHead = head.next

    while (newHead !== null){
      let temp = newHead.next
      newHead.next = head
      newTail.next = temp
      head = newHead
      newHead = temp
    }

return head
};

Question 6

What is an AVL tree?

Answer 6

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

Question 7

What type of ordered does a stack have?

Answer 7

last-in first-out LIFO

Question 8

What type of ordering does a queue have?

Answer 8

first-in first-out FIFO

Question 9

What is the difference between a binary search tree and a binary tree?

Answer 9

A binary search tree imposes the condition that, for each node, its left descendents are less than or
equal to the current node, which is less than the right descendents.

A binary tree does not follow this order of placing nodes. larger numbers and smaller number appear both on the left and right

The definition of a binary search tree can vary slightly with respect to equality. Under some definitions,
the tree cannot have duplicate values. In others, the duplicate values will be on the right
or can be on either side. All are valid definitions, but you should clarify this with your interviewer.

Question 10

What is a complete binary tree?

Answer 10

A complete binary tree is a binary tree in which every level of the tree is fully filled except for perhaps the last level. To the extent that the last level is filled, it is filled left to right.

All the nodes of the tree must be filled. However the most right node of the right branch can not be filled and it is still considered complete.

Question 11

What is a full binary tree?

Answer 11

A full binary tree is a binary tree in which every node has either zero or two children. That is, no nodes have
only one child.

Question 12

What is a perfect binary tree?

Answer 12

A perfect binary tree is one that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes.

Question 13

What is are Tries (Prefix Trees)?

Answer 13

A trie is a variant of an n-ary tree in which characters are stored at each node. Each path down the tree may
represent a word.