Trees – II Non-Recursive PreOrder Traversal Expression Trees Binary Search Tree - Searching - Insertion - Traversal - CreationCarry out a pre-order traversal of this tree void preorder(struct tree_node * p) { if (p !=NULL) { printf(“%d”, p->data); preorder(p->left_child); preorder(p->right_child); } } M P R Q T M P Q R TPreorder Traversal: M P R S Q T M P Q R T SCarry out in-order traversal of this tree void inorder(struct tree_node *p) { if (p !=NULL) { inorder(p->left_child); printf(“%d\n”, p->data); inorder(p->right_child); } } IN ORDER TRAVERSAL: R P M T Q M P Q R TIn ORDER TRAVERSAL : R P S M T Q M P Q R T SNon Recursive implementation of preorder tree traversal In a preorder traversal, we visit the root node first, then we visit its left subtree (all the nodes) and finally visit its right subtree. How do we actually visit all the nodes of a subtree? We can write a non-recursive algorithm by making use of a stack. To start with we push the root node on the stack. Then we push the right child and the left child of the current node on a stack recursively. Then we pop them and print them. Look at this implementation: *p = root; if (p != NULL) { push(p); while ( stack not empty) { p = pop stack; printf(“%d “,p->data); if ( p->right_child != NULL) push ( p-> right_child); if (p ->left_child != NULL) push (p -> left_child); } } /* note the left child is pushed on top of right node, so that it gets popped up first */Non Recursive Preorder Traversal: M P Q R T SStack position Popped values M M Q P Q M P Q S R Q S M P R Q M P R S M P R S Q T - M P R S Q TExpression Trees Many compilers make use of trees, as they serve as ideal representations for the hierarchical structure of a program. Design of a compiler is a complex process, which you shall learn in a later course. Let us look at one particular aspect of compiler, which deals with evaluation of arithmetic expressions. An arithmetic expression can be represented as a binary tree. Such a tree is called an Expression Tree. An expression tree is a binary tree representing an arithmetic expression where the leaf nodes of the tree represent the operands (variables or constants) and the internal nodes and the root node represent the operators. Constructing an Expression Tree Constructing an expression tree involves two parts: Lexical Analysis: Dividing the input into tokens, each of which represents either integer constant, an operator or a variable name. Parsing: Determining if the individual tokens represent a legal expression and finding out the structure of that expression. Generating an expression tree from an infix expression is not very difficult if there is no ambiguity in the expression and it is overly parenthesized. Example : 3 + 5 / 9 + 8 could mean(3 + ( 5/9 ) + 8 ) or ( 3 + 5 / ( 9 +8)) There will be one distinct expression tree for each of the interpretations depending on the parsing scheme. In this section we consider building an expression tree given the expression in its postfix form. The construction starts with reading the postfix expression one symbol at a time. If the symbol is an operand , we create a one-node tree and push it onto a stack. If the symbol is an operator, we pop two trees T1 and T2 from the stack (popping up T1 first), and form a new tree with the operator as the root, T2 as the left child and T1 as the right child. The new tree is then pushed onto the stack. As an example, let the input expression be a b + The first two symbols are operands. So we create one node trees and push them onto a stack.The next symbol is an operator +, so the two one node trees are popped, and a new tree is formed. The first tree to be popped is the one containing b, so this becomes the right child of the operator, the second tree to be popped contains the operand a , and this becomes the left child of the operator. abThe expression tree is now constructed. It is obvious that he evaluation of the expression is nothing but in-order traversal to yield a + b. Let us take a larger expression: a b + c d e + * * Let us say we have processed the first three tokens, and have already reached the ‘+’ operator. a b +Next we read c, d, e and construct one node trees and push them onto the stack. Next is an operator ‘+’, so last two trees are popped out and a new tree formed with this as root. a b + c d eNext symbol is another operator ‘*’, so again two trees are popped from the stack and merged to form a new tree with this operator at the root: a b + c d e + +Finally the last operator ‘*’ causes the last two entries from the stack to be pulled out , i.e. the tree containing ‘+’ at the root and the tree containing ‘*’ at the root. These are merged with the second ‘*’ operator as the root, and the expression tree is complete, and now it is the only entry in the stack. a b + c ++ * d eLet us now see how do we evaluate this tree. int eval (struct tree_node *p) { int lhs, rhs; char op; if ( p -> left_child = NULL && (p-> right_child = NULL) return ( p->data); else lhs = eval( p ->left_child); rhs = eval( p ->right_child); op = p ->data; switch (op) { case ‘+’: return (lhs+rhs); case ‘-’: return (lhs-rhs); case ‘*’: return (lhs*rhs); case ‘/’: return (lhs/rhs); } Binary Search Tree (BST)We have seen earlier that if the values in nodes of a binary tree are arranged in a specific order, with all elements smaller than the root stored in left subtree and all elements greater than the root stored as right subtree, it represents a sorted list. The search complexity reduces considerably, as the height of the tree is much less than total number of elements. Of course, one has to keep in mind that the tree has to be organized in a specific manner. Such a tree is known as a Binary Search tree, because it permits us to carry out a search similar to the Binary search method that we have used on a sorted array. Let us first of all define a BST. A Binary search tree (BST) is a binary tree that is either empty , or each node contains a data value satisfying the following: a) all data values in the left subtree are