Suppose that x is a node in a binomial tree within a binomial heap, and assume that sibling[x] ≠ NIL. If x is not a root, how does degree[sibling[x]] compare to degree[x]? How about if x is a root?

__Answer:__

- If x is not a root.

By definition of B5.2 (page 1088): The number of children in a node x in a rooted tree T is called the degree of x.

Also if two nodes have the same parent, they are siblings.

**(a) (b)**

If sibling[x] is immediate to the right
of x (see (**a**) above) then:

Degree[sibling[x]] = degree[x] - 1

If sibling[x] is immediate to the left
of x (see (**b**) above) then:

Degree[sibling[x]] = degree[x] + 1

- If x is a root.

From the **min-heap property**
(page 129) is that for every node i other than the root A[PARENT(i)] ≤ A[i].
The smallest element in a min-heap is at the root.

Also root x is linked to its
sibling (root) together known as **linked list.** The degree of the roots
strictly increase as we traverse the root list è degree of x cannot be
equal to its immediate right root.

Therefore if x is a root then degree[x] < degree[sibling[x]]

If x is a none root node in a binomial tree within a binomial heap, how does degree[x] compare to degree[p[x]]?

__Answer:__

The degree[p[x]] contains the pointer to it parent , that means degree[p[x]] = degree[x] + P (some value of P).If x is the most left child then

degree[p[x]] = degree[x] + 1.

Other word degree[p[x]] is always greater than degree[x]:

degree[p[x]] > degree[x]

Suppose we label the nodes of binomial tree B_{k} in
binary by a postorder walk, as in figure 19.4. Consider a node x labeled l at
depth i, and let j = k – i . Show that x has j 1’s in its binary
representation. How many binary k-strings are there that contains exactly j 1’s
? Show that the degree of x is equal to the number of 1’s to the right of the
right most 0 in the binary representation of 1’s.

__Answer:__