u3

Question 1

The three laws of recursion:

Answer 1

• A recursive algorithm must have a base case.
• A recursive algorithm must change its state and move towards the base case.
• A recursive algorithm must call itself

Question 2

binary tree

Answer 2

a tree in which each node has a maximum of two children and each child of a node is designated as the left or right child

Question 3

Preorder

Answer 3

root, then left subtree,then right subtree.

Question 4

Inorder:

Answer 4

left subtree, then root, then right subtree.

Question 5

complete binary tree

Answer 5

a binary tree in which all parents have two children, except for the parents of children at the bottom level of the tree. At the bottom level, all nodes must be as far to the left as possible.

Question 6

binary heap

Answer 6

a complete binary tree with an ordering rule (the heap order property) which states that parent nodes are either less than or equal to their children (a min heap) or greater than or equal to their children (a maxheap).

Question 7

Heapifying

Answer 7

the process of creating a binary heap from a list.Heapifying is possible in O(n) time.