The following function is applied onto a graph and it specifically implements the method of breadth-first search. To visit all nodes connected to node k of a graph, we put the k in a FIFO queue and then go into a loop, during which we get the next node from the queue and, if we have not already visited it, we visit it and push into the queue all nodes belonging to the adjacency list of this node, continuing this process until we empty the queue.

## Archive for March 31, 2011

The following program creates the syntax tree of a mathematical expression in prefix notation. For simplicity, we assume that the terms of the expression are individual characters (digits). Each time the recursive function parse() is called, a new node is created, whose value is the next character of the expression. If the value is a term (digit), we return the new node. However, if it is an operator, we set the left and right pointers to point the tree made (recursively) for the two operands.

The iterative (non-recursive) function preorderTreeTraverse() can perform preorder traversing of a binary tree with the help of a stack that can hold pointers to nodes of the tree.

Also, the iterative (non-recursive) function layerTreeTraverse() can perform level-order traversing of a binary tree with the help of a queue that can hold pointers to nodes of the tree.

To calculate a prefix expression, we either convert a number from ASCII to decimal (in the loop ‘while’ at the end of the program) or implement the operation indicated by the first character of the expressions to the two terms, with a recursive calculation. This function is recursive, but it uses a global array containing the expression and an index number for the current character of the expression. The index number goes beyond each sub-expression calculated.

The elegant recursive solution to a problem is most of the times invaluable. Although the iterative solution of that problem is likely to have a better space and time complexity, it is often preferred to use the recursive version for clarity and simplicity. It is remarkable how easily a problem can be solved by use of a recursive manner. In this article we will try to record a collection of useful recursive functions: