The nodes of a every non-empty binomial tree of order k can be recursively labeled so that each node has a unique k-bit binary label as follows: If k = 1, the root is labeled 0 and the child is labeled 1: for general k, take the labels of the leftmost subtree (of order k-1) and append “1” to left of every node label, while for the remaining nodes (i.e., the nodes of the other copy of the binomial tree of order k-1), append “0” to left of every node label. a. What is the label of the root? b. Prove that the depth of every node is the number of 1’s in its binary label. c. Prove that the binary label of the parent of any node x can be derived by zeroing out the rightmost “1” in the binary label of x.
