Trees are made of vertices and edges, also called nodes and edges. The set of vertices of a tree is called V, and the se

[answerhappygod]

Trees are made of vertices and edges, also called nodes andedges. The set of vertices of a tree is called V, and the set ofedges is called E. A non-empty binary tree T is either 1. a rootnode R, or 2. a root node R attached by an edge to either one ortwo of the nodes R1 and R2, where R1 and R2 are the roots ofnon-empty binary trees T1 and T2, respectively. Define the heightof a tree to be the maximum number of edges in the shortest pathbetween a leaf and the root. Prove by structural induction: For anynon-empty binary tree T with height h and n nodes, n ≤ 2 h+1 − 1.Notes: 1) You must use the rules above to generate your trees. 2)There are two options for the tree numbered in the definition. Oneof those will be your base case, the other will let you know whatstructures you will need to make an inductive assumption for. 3) Itis fine to do a WOLOG to say the left subtree is taller than theright. 4) Since the two subtrees are named T1 and T2, it makes iteasier for the audience if T1 has n1 nodes and height h1 forexample. 5) You definitely need to have inequalities as asignificant part of your proof. Your proof is not going to be justa paragraph of all words.