Homework $3$

Problem $1.$ A full node of a binary tree is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.

Problem $2.($a$)$ Show the result of inserting $5,1,7,11,15,4,9,12$ into an initially empty binary search tree.

$($b$)$ Show the result of deleting the element at the root.

Problem $3.$ Show the result of inserting $5,3,46,53,120,13,61,77$ into an initially empty AVL tree.

Problem $4.$ An AVL tree $T$ is stored using class AvlNode. Design a linear$-$time algorithm that verifies $T.$ Check that $T$ is a binary search tree. Check that height of each node is correct. Check that each node is balanced.

Problem $5.($a$)$ Find the smallest order of the B$-$tree shown below. What is the smallest $L?$

$($b$)$ Insert $24$ and $26$ into the B$-$tree shown below. Assume the smallest order and $L.$