Question: Given the root pointer to a binary tree, find if an element is present in it. Input: Sample Tree (Pointer to node 1 is given), Search – 3 Output: Present One simple way of solving this problem is to find the element in the left subtree, in the right subtree, and in the root data. This approach can be easily implemented with recursion. This approach works because each node of the tree has 3 parts > the root, the left and the right. What we do is we see…
Recursion
Algorithms involving recursion


Question: Given the root pointer to a binary tree, find the maximum element present in it. Input: Sample Tree (Pointer to node 1 is given) Output: Maximum = 9 One simple way of solving this problem is to find the maximum element in the left subtree, find maximum in the right subtree, compare it with the root data and select the one that gives the maximum value. This approach can be easily implemented with recursion. This approach works because each node of the tree has 3 parts > the root,…

We discussed about the basic tree traversals in this post – Binary Tree Traversals Lets take our own sample tree for understanding postorder traversal. In PostOrder traversal, the root is visited after both subtrees are completed. Postorder traversal is defined as follows: Traverse the left subtree in postorder. (Step 1) Traverse the right subtree in postorder. (Step 2) Visit the root The postorder traversal can then be defined in this way – The nodes of the tree will therefore be in order – 4, 5, 2, 6, 7, 3, 1…

We discussed about the tree traversal techniques in this post Binary Tree Traversals Please see preorder traversal to understand the basics of visiting nodes. We have our same sample tree Now let us try to understand the Inorder traversal. In inorder traversal, the root is traversed between the sub trees. Inorder traversal is defined as follows. Traverse the left subtree Visit the node Traverse the right subtree So when we apply the inorder traversal on our example tree this will be done as: We get the final inorder traversal as:…

We learned about the different type of traversals in this post Binary Tree Traversals In preorder traversal, each node is processed before (pre) either of its subtrees. This is the simplest traversal to understand. However, even though each node is processed before the subtrees, it still requires that some information must be maintained while moving down the tree. Let us consider an example In the example tree shown above, the node “1” is processed first, then the left subtree, followed by the right subtree. Therefore, processing must return to the…

Question: Find sum of digits in a given number. Input: 65536 Output: 25 Method 1 (Iterative): In this code sample by using modulus operator(%), we extract the individual digits of given number then we add them together Method 2 (recursive):

This algorithm is one of the specific ones people generally have a problem to understand. We will try out best to simplify it and understand it.Basically quick sort comprises of these steps: Choose a pivot element (it can be any random element in array) In one iteration keep all the numbers smaller to it on the left side and larger to it on the right side.(smaller numbers)_ _ _[PIVOT]_ _ _(larger numbers) Now we have the left subarray of (small numbers) and the right subarray (large numbers) Repeat steps 1…

Question: Write a program in C to reverse a string using recursion Input: Hello Everyone Output: enoyrevE olleH We will use the simple concept of recursion to print the string in reversed order. Note that, we will not store the reversed string in any variable, we are just printing the string in reversed order. Recursive function (reversePrint) takes string pointer (str) as input and calls itself with next location to passed pointer (str+1). Recursion continues this way, when pointer reaches ‘\0′, all functions accumulated in stack print char at passed…

Question: You are given a stack and you have to reverse it, using only stack operations push and pop. The algorithm for the above problem can be given in this way: First POP all elements of the stack till it becomes empty Now for each upward step in the recursion, push the elements at the bottom of the stack.

Question: Write a program to reverse a Linked List in pairs. That means we should reverse the 1st and 2nd numbers, 3rd and 4th numbers and so on. Input: 4, 8, 15, 16, 23, 42 Output: 8, 4, 16, 15, 42, 23 The basic idea behind solving this problem is that we need to traverse the entire list and we need to keep on swapping the values of 2 adjacent nodes. Since we need to reverse the values in pairs, it is also clear that we need to move 2…