Trees

Question 1

What is a complete binary tree?

Answer 1

BinTree with all levels full, except bottom level. Last level is filled starting from the left.

Question 2

What is a full binary tree?

Answer 2

BinTree where all nodes have 2 children, other than the leaves

Question 3

how is the height of a tree calculated?

Answer 3

the max level of all nodes

Question 4

how is the level of a node calculated?

Answer 4

numbers of edges from root node!

Question 5

What are the 2 properties of a (min/max) binary heap?

what are the 2 properties referred to as?

Answer 5

1. [shape property] complete binary tree structure
2. [heap property] for min: parents always <= children
   for max: parents always >= children

Question 6

When representing bin-heaps with arrays, which index do you start with for the root node?

Answer 6

start with index 1, instead of index 0

Question 7

How do you find the index of a child?

Answer 7

My child is 2x me

left child = 2p
right child = 2p + 1

Question 8

How do you insert a new value into the binheap list?

Answer 8

append to end of list, then switch values to maintain heap property

Question 9

How do you maintain heap property once you’ve inserted new value to end of list?

Answer 9

Compare value with value of parent;

for min BinHeap, if child smaller than parent, switch child and parent, etc.

Question 10

When we remove the root node (min/max value), how do we preserve the heap property?

Answer 10

move the last item in the list to the front of list, then percolate down

Question 11

How do you percolate down to preserve heap property?

Answer 11

compare parent to 2 children, switch with the child that is larger than parent and other child (max heap)

Question 12

What’s the binary search tree (BST) property?

Answer 12

all left subtree values to a node are smaller than the value in the node
all right subtree values to a node are greater than the value in the node

Question 13

How do preorder, postorder and inorder BST traversal work?

Answer 13

Do this recursively, starting with the root node & its children

Preorder: parent - left child - right child
Inorder: left child - parent - right child
Postorder: left child - right child - parent

Question 14

For the BST, what’s an algorithm for finding a node corresponding to a particular value?
(1st pseudo code, 2nd Python code)

Answer 14

check if first node’s value is EQUAL to the value, if yes, return the node:
else: if node’s value is larger than the value we’re finding, recursively perform function on left child
elif:
do opposite:
else: return None

Question 15

What’s an algorithm for inserting a node with a value into an existing BST?
(1st pseudo code, 2nd Python code)

Answer 15

1st:
check if the value is the same as the value of the current node (we can only insert unique values?)
if yes, return (do nothing)

2nd:
check if the value is smaller than the value in the current node
if it is, check if a left child exists:
if yes, recursively call inserting function, using that left child as current node i.e. self.left.insert(value)
if no, make new left child BST object with self.left = BST(value, parent = self)

repeat for checking if the value is larger than the value in the current node

Question 16

What’s an algorithm for creating a BST using elements from a list?
(1st pseudo code, 2nd Python code)

Answer 16

def create(a_list):

1st make root node BST object using the first element
2nd iteratively use the insert function for every other element in the given list

Question 17

What’s an algorithm for deleting a value in a BST, without any children?

Answer 17

2 (bigger) cases:

a) not deleting a value from a root node

i) check if a node has a parent:
if yes => check if the root node is left the child or right child
if left, set self.parent.left = None
if right, set self.parent.right = None

b) deleting value from root node

simply set root node’s value to None (self.value = None)

Question 18

What’s an algorithm for deleting a value in a BST, with one child?

Answer 18

don’t want to remove root node bc otherwise we have no BST

Make set a variable ‘child’ to self.left or self.right

1. Check if value is root node or not

If not root node:
see if current is parent’s left or right child
set child to parent’s left or right child

If root node, replace root node value with the child, using a method: def replace(self, other)

Question 19

What’s an algorithm for deleting a value in a BST, with two children?

Answer 19

Find the inorder successor node
- go to the right child, go down to find node with maximum of 1 child
connect successor’s child to successor’s prev parent

Question 20

What’s an efficient way to construct a BinHeap from a list?

Answer 20

Start half-way through the list (all leaves, or one edge from a leaf)
Percolate down for all nodes, until you reach the root node