[Solved]Definition Full Binary Tree Fbt One Single Node T1 T2 T1 T2 Fbt S Two Trees Joined Togethe Q37247499

Definition. A full binary tree (FBT) is one of: – • (a singlenode), or – T1 ∧ T2, where T1 and T2 are FBT’s (two trees joinedtogether with one new root and two new edges).

Define the function nodes : FBT → N that counts the number ofnodes in a FBT as follows:

nodes(T) = 1 if T = •

nodes(T) = nodes(T1) + nodes(T2) + 1 if T = T1 + T2 for FBT’s T1and T2 1.

(a) Write a recursive definition of the function edges : FBT → Nthat calculates the number of edges in a tree.

(b) Using your definition of edges, prove the following claim:Claim. Every full binary tree has an even number of edges.

(c) Using your definition of edges, prove the following claim:Claim. For every full binary tree t, nodes(t) = edges(t) + 1.

Expert Answer

---

Answer to Definition. A full binary tree (FBT) is one of: – • (a single node), or – T1 ∧ T2, where T1 and T2 are FBT’s (two … . . .