Recursion

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 sub-tree, in the right sub-tree, 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…

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 sub-tree, find maximum in the right sub-tree, 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 post-order traversal. In Post-Order traversal, the root is visited after both sub-trees are completed. Post-order traversal is defined as follows:- Traverse the left sub-tree in post-order. (Step 1) Traverse the right sub-tree in post-order. (Step 2) Visit the root The post-order 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 pre-order traversal to understand the basics of visiting nodes. We have our same sample tree Now let us try to understand the In-order traversal. In in-order traversal, the root is traversed between the sub trees. In-order traversal is defined as follows. Traverse the left sub-tree Visit the node Traverse the right sub-tree So when we apply the in-order traversal on our example tree this will be done as:- We get the final in-order traversal as:-…

We learned about the different type of traversals in this post Binary Tree Traversals In pre-order traversal, each node is processed before (pre) either of its sub-trees. This is the simplest traversal to understand. However, even though each node is processed before the sub-trees, 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 sub-tree, followed by the right sub-tree. 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 sub-array of (small numbers) and the right sub-array (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…