7.3. BINARY TREES 1087.3. Binary Trees7.3.1. Binary Trees. A binary tree is a rooted tree in which eachvertex has at most two children, designated as left child and right child.If a vertex has one child, that child is designated as either a left childor a right child, but not both. A full binary tree is a binary tree inwhich each vertex has exactly two children or none. The following area few results about binary trees:1. If T is a full binary tree with i internal vertices, then T has i+1terminal vertices and 2i + 1 total vertices.2. If abinary tree of height h has t terminal vertices, then t ≤ 2h.7.3.2. Binary Search Trees. Assume S is a set in which elements(which we will call “data”) are ordered; e.g., the elements of S can benumbers in their natural order, or strings of alphabetic characters inlexicographic order. A binary search tree associated to S is a binarytree T in which data from Sare associate with the vertices of T sothat, for each vertex v in T , each data item in the left subtree of v isless than the data item in v, and each data item in the right subtree ofv is greater than the data item in v.Example: Figure 7.10 containsa binary search tree for the set S ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. In order to find a element we start at the rootand compare it to the data in the current vertex (initially the root).If the element is greater we continue through the right child, if it issmaller we continuethrough the left child, if it is equal we have foundit. If we reach a terminal vertex without founding the element, thenthat element is not present in S.5213 7691084Figure 7.10. Binary Search Tree.7.3. BINARY TREES 1097.3.3. Making a Binary Search Tree. We can store data ina binary search tree byrandomly choosing data from S and placingit in the tree in the following way: The first data chosen will be theroot of the tree. Then for each subsequent data item, starting at theroot we compare it to the data in the current vertex v. If the newdata item is greater than the data in the current vertex then we moveto the rightchild, if it is less we move to the left child. If there isno such child then we create one and put the new data in it. Forinstance, the tree in figure 7.11 has been made from the following listof words choosing them in the order they occur: “IN A PLACE OF LAMANCHA WHOSE NAME I DONOT WANT TO REMEMBER”.AIDOWHOSEPLACEOFINLAREMEMBERTOWANTMANCHANAMENOTFigure 7.11. Another binary Search Tree.7.3.4. Tree Transversals. In order to motivate this subject, weintroduce the concept of Polish notation. Given a (not necessarilycommutative) binary operation ◦, it is customary to represent the resultof applying the operation to two elements a, b by placing the operationsymbol in the middle:a ◦ b .This is calledinfix notation. The Polish notation consists of placingthe symbol to the left:◦a b .The reverse Polish notation consists of placing the symbol to the right:a b ◦ .The advantage of Polish notation is that it allows us to write ex-pressions without need for parenthesis. For instance, the expressiona∗(b+c) in Polish notation would be ∗a + b c, while a ∗b + c is +∗a b c.Also, Polish notation is easier to evaluatein a computer.7.3. BINARY TREES 110In order to evaluate an expression in Polish notation, we scan theexpression from right to left,placing the elements in a stack.1Eachtime we find an operator, we replace the two top symbols of the stackby the result of applying the operator to those elements. For instance,the expression ∗+ 2 3 4 (which in infix notation is “(2 + 3) ∗4”) wouldbe evaluated like this:expression stack∗ + 2 3 4∗+ 2 3 4∗ + 2 3 4∗ + 2 3 4∗ 5 420An algebraic expression canbe represented by a binary rooted treeobtained recursively in the following way. The tree for a constant orvariable a has a as its only vertex. If the algebraic expression S is ofthe form SL◦ SR, where SLand SRare subexpressions with trees TLand TRrespectively, and ◦ is an operator, then the tree T for S consistsof ◦ as root, and the subtrees TLand TR(fig. 7.12).oTLTRFigure 7.12. Tree of S1◦ S2.For instance, consider the following algebraic expression:a + b ∗ c + d ↑ e ∗ (f + h) ,where + denotes addition, ∗ denotes multiplication and ↑ denotes ex-ponentiation. The binary tree for this expression is given in figure 7.13.1A stack or last-in first-out (LIFO) system, is a linear list of elements in whichinsertions and deletions take place only at one end, called top of the list. A queueor first-in first-out (FIFO) system, is a linear list of elements in which deletionstake place only at one end, called front of the list, and insertions take place onlyat the other end, called rear of the list.7.3. BINARY TREES 111+*+d ef h*b c+aFigure 7.13. Tree for a + b ∗ c + d ↑ e ∗ (f + h).Given the binary tree of an algebraic expression, its Polish, reversePolish and infix representation are different ways of ordering the ver-tices of the tree, namely in preorder, postorder and inorder respectively.The following arerecursive definitions of several orderings of theverticesof a rooted tree T = (V, E) with root r. If T has only onevertex r, then r by itself constitutes the preorder, postorder and inordertransversal of T . Otherwise, let T1, . . . , Tkthe subtrees of T from leftto right (fig.7.14). Then:rT1 T2...TkFigure 7.14. Ordering of trees.1. Preorder Transversal: Pre(T ) = r, Pre(T1), . . . , Pre(Tk).2. Postorder Transversal: Post(T ) = Post(T1), . . . , Post(Tk), r.3. Inorder Transversal. If T is a binary tree with root r, left sub-tree TLand right subtree TR, then: In(T ) = In(TL), r,