Microsoft Word – Section 2 Solutions.docx
Section 2 Solutions
1.
Base case: A tree with height, H = 0(the smallest perfect binary tree) has an odd number of
nodes, N0 = 1.
Inductive hypothesis: Assume for a perfect binary tree of height H = K, the number of nodes at
height k, Nk, is odd.
Inductive step: Show that for the H = k + 1, Nk+1 is odd.
To increase the height of a perfect binary tree by 1(from K to K + 1), we need to add 2 child
nodes to every leaf node in order to keep it perfect. Thus Nk+1= Nk + 2(L), where L is the number
of leaves in Nk
Nk (odd) + 2(L) (even) = Nk+1(odd)
Conclusion: the number of nodes in a perfect binary tree is odd.
2.
A.
I. O(N)
II. O(N)
III. O(logN)
IV. O(N2)
B. logN, N, N, N2
3.
4.
F
/ \
A B
/ \ /
E D C
Pre-Order: FAEDBC
5.
int countNodes(TreeNode root) {
return root == null ? 0 : 1 + countNodes(root.left) + countNodes(root.right);
}
6.
public push(int x) {
Node n = new Node(x, tail.prev, tail);
tail.prev.next = n;
tail.prev = n;
}
public int pop() {
if (head.next == tail)
{
throw new EmptyStackException();
}
int result = tail.prev.data;
tail.prev=tail.prev.prev;
tail.prev.next=tail;
return result;
}
7.
A.
B. Pick minimum value from right subtree
2
\
5
/ \
3 7
/ \
6 8