程序代写代做代考 Microsoft Word – Section 2 Solutions.docx

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