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
Posted: Thu Jul 07, 2022 2:20 pm
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 any non-empty binary tree T with height h and n nodes, n ≤ 2h+1 − 1. Notes: 1) You must use the rules above to generate yourtrees. 2) There are two options for the tree numbered in thedefinition. One of those will be your base case, the other will letyou know what structures you will need to make an inductiveassumption for. 3) It is fine to do a WOLOG to say the left subtreeis taller than the right. 4) Since the two subtrees are named T1and T2, it makes it easier for the audience if T1 has n1 nodes andheight h1 for example. 5) You definitely need to have inequalitiesas a significant part of your proof. Your proof is not going to bejust a paragraph of all words.