Trees

Question 1

What is a binary tree?

Answer 1

A tree whose elements have at most 2 children (left and right child)

Question 2

How are binary trees stored in memory?

Answer 2

Each node has a pointer to parent (or NULL/itself if root), pointer to left/right child (or NULL/itself if there isn’t one), and a value representing the item stored in the node

Question 3

How do you search a binary tree?

Answer 3

Start at the root and search the tree level-by-level (top to bottom, left to right)
This has time complexity O(n)

Question 4

What is a binary search tree?

Answer 4

A binary tree where for every node (with value v), all elements in the left sub-tree are smaller than v and all elements in the right sub-tree are bigger than v

Question 5

Preorder vs inorder vs postorder tree traversal

Answer 5

Preorder = print(root), preorder(left), preorder(right)
Starts with root, goes all the way left, ends with rightmost

Inorder = preorder(left), print(root), preorder(right)
Starts with leftmost, ends with rightmost, items in sorted order

Postorder = preorder(left), preorder(right), print(root)
Starts with leftmost, ends with root

Question 6

Inserting into a BST

Answer 6

Call the .insert() function on the root
This function:
Compares the new value to the root
If it’s less than the root, recurses into the left subtree
If it’s greater than the root, recurses into the right subtree
If the left/right subtree doesn’t exist, it appends the new value there

Question 7

Searching a BST

Answer 7

Call the .lookup(n) function on the root
If this is a match, return it and its parent
If our target is smaller, recurse into the left sub-tree, otherwise recurse into the right sub-tree

Question 8

Deleting from a BST

Answer 8

Call root.delete(n)

No children: simply remove n

One child: Transfer child’s value to n and then delete child

Two children: Find the smallest node v that’s bigger than n, copy v’s data into n, and then delete v

Question 9

Time complexity of searching, inserting and deleting

Answer 9

Average: O(h) = O(log(n))
Worst: O(n)

Question 10

Finding the smallest element in a BST

Answer 10

Always go left

Question 11

Finding the smallest element bigger than a given node in a BST

Answer 11

Start at that node, go right once and then always go left. Stop when you hit NULL.

Question 12

What is an AVL tree?

Answer 12

One where a given node’s subtrees do not differ in height by more than 1

Question 13

Tree.LeftRotate(x)

Answer 13

Remove x.right.left and store for later
Replace x with x.right
The new x.left should now be empty
x.left = old x, left: old x.left, right: old x.right.left

Question 14

What is trinode restructuring

Answer 14

A combination of rotations, applied to a parent, child, and grandchild (z, y, x) depending on whether the child and grandchild are on the same side

Question 15

Trinode restructuring: single rotation (child and grandchild on same side)

Answer 15

Assuming both right:
Tree.LeftRotate(z)

Question 16

Trinode restructuring: double rotation (child and grandchild on opposite sides)

Answer 16

Assuming right left:
Tree.RightRotate(y)
Tree.LeftRotate(z)
The middle one out of x,y,z always ends up as the root of the subtree

Question 17

Height of an AVL tree storing n keys

Answer 17

O(log(n))

Question 18

How to perform post-insertion fix-up

Answer 18

From the newly-inserted node p, find the lowest node which is unbalanced. If one exists, name it z and do trinode restructuring on z, y, and x.
You can stop when you reach a node whose height didn’t change

Question 19

How to perform post-deletion fix-up

Answer 19

Let p be the parent of the deleted node
From p, start searching for z (the first unbalanced node)
Let y be the taller child of z
Let x be the taller child of y (or if the children have the same height, on the same side as y)
Keep going up the tree, restructuring when you meet an unbalanced node
You can stop when you reach a node whose height didn’t change, or when restructuring results in the same height as before insertion/deletion

Question 20

AVL tree performance

Answer 20

Uses O(n) space to store n items
Restructuring = O(1)
Searching = O(log(n))
Insertion and removal = O(log(n)) for find + O(log(n)) for restructuring = O(log(n)) overall

Question 21

What is a priority queue

Answer 21

Data structure where each element is a tuple (key-value pair) and the key is an integer representing the priority of that item

Question 22

Priority queue operations

Answer 22

P.add(k, v): Insert an item with key k and value v
P.min(): Return the tuple (k, v) with the lowest priority
P.remove_min(): Remove P.min() from the queue and return it
P.is_empty()
len(P)

Question 23

What is a heap

Answer 23

A data structure like a tree, except they are stored in a flat array
The tree has to complete except for the lowest level
HeapSize(A) = number of elements in heap stored in A
Height of a heap = floor(log(len(A)))

Question 24

Max-heap vs Min-heap

Answer 24

Max-heap: Every node’s value is less than than or equal to its parent
Min-heap: Every node’s value is greater than or equal to its parent

Question 25

Inserting into a max-heap H

Answer 25

Step 1: Add the new element node to the bottom-left node on the left side Step 2 (heapify): If the new node value is bigger than its parent, swap their values and set the parent node as the new node. Repeat this step until the new node value is smaller than the parent

Question 26

Array indices

Answer 26

Root is in A[1] i.left = A[2i] i.right = A[2i + 1] i.parent = A[floor(i/2)]

Question 27

Heapification

Answer 27

Heapify(A, v, n): A = array, v = largest, n = length Starting at the root, identify largest out of the current node (v) and its children, let the largest element be w. Exit if leaf If v =/= w, swap A[w] and A[v] and then recurse into what used to be v Running time: O(log(n))

Question 28

Building a heap from array A

Answer 28

for i=len(A) downto 1: Heapify(A, i, n) Running time: O(n)

Question 29

Extraction (deletion) from a heap

Answer 29

Elements are always deleted from the root of the heap Step 1: Replace the root node's value with the last node's value so that H is still a complete binary tree Step 2: Delete the last node Step 3: Move the new root node's value down until H satisfies the heap property

Question 30

HeapSort

Answer 30

Call BuildHeap on unsorted data For i = Length(A) downto 2: Swap A[i] and A[1] Reduce HeapSize by 1 Heapify(A, 1, HeapSize(A)) Time complexity: O(n*log(n))

Question 31

What is a decision tree?

Answer 31

A full binary tree (all nodes have either 0 or 2 children) representing all comparisons between n elements made by a given algorithm Internal nodes are labelled i:j meaning elements i and j are compared Downward edges are marked with < or > Leaves are labelled with some permutation of {1, ..., n} (n! leaves) Correct sorting algorithms must be able to produce each permutation of input

Question 32

Lower bound for worst case using decision trees

Answer 32

The length of the longest path from the root to a leaf represents the worst case number of comparisons for that value of n

Question 33

Using decision trees, prove that any comparison-based algorithm requires Ω(n*log(n)) comparisons in the worst case

Answer 33

Consider a decision tree of height h with L leaves corresponding to a comparison sort of n elements Since each of the n! permutations appears as a leaf, L >= n! A binary tree of height h has at most 2^h leaves: L <= 2^h n! <= L <= 2^h, therefore 2^h >= n! h >= log(n!) = Ω(n*log(n))

Question 34

What is an adversary

Answer 34

An algorithm that dynamically constructs bad inputs for an algorithm to test its running time When the search algorithm accesses its input data (e.g. if i[2] < i[3], do blablabla) it generates a response It gives answers so that there's always a consistent input It helps us find the lower bound on the runtime of an algorithm

Question 35

Proof that finding the max element in an unsorted array takes n-1 comparisons

Answer 35

After n-2 comparisons, 2 elements have never lost a comparison, therefore there is not enough info to tell which one is bigger

Question 36

Algorithm for finding the 2nd largest item in an unsorted list

Answer 36

Finds max in n-1 comparisons, there are ceil(log_2(n)) elements which lost directly to max. 2nd largest overall is largest out of these Finding the largest out of these takes ceil(log_2(n)) - 1 comparisons Altogether, this takes n + ceil(log_2(n)) - 2 comparisons

Question 37

Number of comparisons needed to find kth largest in array of size n

Answer 37

V(n, k) >= n - k + ceil(log_2(n choose k-1))