The following pictures illustrate how to code an unlabled binary tree, using a formula to ecode the node number. The coding process starts from the leaves.

a.) prove that the method correctly encodes unlabeled binary trees. (I belive that this is a bijection proof)

b.) Show how to un-encode

the tree from the number given to the root. (This is different than Pr ?ufers

method) Please explain each etep clearly, and do both parts for a thumbs up.

Otherwise it will be marked as incomplete. Thanks.

ChildrenLabel Label tips with 1 Binary case: each node has 2 children 1, 1 2, 1 (2,2) oProceed from root to tip o Each node is labelled according (3,2) (3,3) to its childrens' labels 7 2 children with labels k,j, ordered: k j Sort lexicographically (k.j) (k-1) +j+1 ChildrenLabel Label tips with 1 Binary case: each node has 2 children 1, 1 2, 1 (2,2) oProceed from root to tip o Each node is labelled according (3,2) (3,3) to its childrens' labels 7 2 children with labels k,j, ordered: k j Sort lexicographically (k.j) (k-1) +j+1