Microsoft Word – Section 1 Solutions.docx
Section 1 Midterm Solutions
1.
Base case: a tree with one node(the smallest full binary tree) will have NI = 0 internal nodes and
NL = NI + 1 = 1 leaf node
Inductive hypothesis: Assume for a number of internal nodes, NI = K, there are NL = K + 1
leaves
Inductive step: Show that for the NI = K + 1, NL = (k + 1) + 1
To increase the number of internal nodes by 1(from K to K + 1), we need to turn one of the leaf
nodes to an internal node by adding two child nodes to it(we need to add two child nodes
because nodes in a full tree must have 0 or 2 children).
𝛥NI = +1, 𝛥NL = +2 – 1 = +1 (The two child nodes we added – the leaf node turned to an internal
node)
Thus, NI = k+1 and NL = (k + 1) + 1
Conclusion: NL = NI + 1 holds for all full binary trees.
2.
A.
I. O(N)
II. O(logN)
III. O(2N)
IV. O(N)
B. 2N, N, N, logN
3.
4. B
/ \
A D
/ \ \
C E F
Post: CEAFDB
5.
int calcHeight(TreeNode root) {
return root == null ? -1 : 1 + Math.max(calcHeight(root.left),calcHeight(root.right));
}
6.
public void enqueue(int x)
{
Node n = new Node(x, head, head.next);
head.next.prev = n;
head.next = n;
}
public int dequeue()
{
if (tail.prev == head)
{
throw new EmptyQueueException();
}
int result = tail.prev.data;
tail.prev.prev.next = tail;
tail.prev = tail.prev.prev;
return result;
}
7.
A.
B. Pull largest number from left subtree
7
/
1
\
3
/ \
2 6
/
5