Recursion

The first thing that comes to our mind on hearing the word recursion is doing a thing over and over again. But how can you expect to achieve a solution to a problem by repeating the same thing over and over again. In this post we would be understanding exactly that. Algorithmic paradigms are a way to solve a problem, and recursion is one of them. Some of the other ways are: Brute Force Divide and Conquer Greedy Dynamic Programming So, what is Recursion? Sometimes a good image helps to…

Dynamic programming always reminds of a favorite quotation: Of the several different ways to solve a problem, dynamic programming is a paradigm where we tend to solve the problem as we move ahead and keep on learning. This is one of the techniques which even seasoned programmers find hard to implement. In this post we will try to address some of these fears and aim to have a better understanding of this approach. If you are new to problem solving and somehow landed at this post, it is recommended to…

You are provided with a binary tree, return the length of the diameter. The diameter of the binary tree is defined as the length of the longest path between any two nodes in the tree. In the above example the diameter of the binary tree is 7. Problem Statement: We can easily find out the distance between two nodes in a binary tree. In the given example, the distance between node 5 and 8 is 4. The distance between node 2 and 6 is 3, the distance between node 8…

Question: Given 2 binary trees, determine if they are mirror of each other Input: 2 tree pointers are given. (Root pointer) Output: TRUE We can again apply the recursive sub-structure property of the tree here. The algorithm can be implemented as:- Time Complexity:- O(n) Space Complexity:- O(n) due to a recursive stack

Question: Given the root pointer to a binary tree, find the sum of all its elements. Input: Sample Tree (Pointer to node 1 is given). Output: Sum = 15 This is a very simple problem. Since the tree follows a recursive sub-structure, we can recursively call left tree sum, right tree sum and then add their values to the current node data.

Question: Given a binary tree, find its mirror tree. Input: A tree pointer is given. (Root pointer) Output: Pointer of mirrored tree. We can easily get the mirrored tree by a simple recursive algorithm. We traverse the tree and swap the left and right pointers. Time Complexity:- O(n) Space Complexity:- O(n) (due to recursive stack)

Question: Given two binary trees, find if they are structurally identical. Input: 2 trees are given. (Root pointers) Output: TRUE When we say structurally identical trees, we mean that both the trees have exactly the same number of nodes, arranged in the exactly same way. It is not necessary that the value of each node should also be the same. Since, we need to traverse each node of the tree and each node has the same property of having a data value, a left child and a right child, we…

Question: Given the root pointer to a binary tree, find the height. Input: Sample Tree (Pointer to node 1 is given). Output: 3 The method we will learn relates to the same method we discussed in the post how to find the size of a binary tree – Find the size of a binary tree In the above post we applied a recursive approach because the tree follows a recursive property. Every node has the same property. It has a root value, a left pointer and a right pointer. This…

Question: Given the root pointer to a binary tree, delete the binary tree Input: Sample Tree (Pointer to node 1 is given). To delete a tree we must traverse all the nodes of the tree and delete them one by one. So which traversal should we use ? Inorder, Pre-order, Post-order or Level Order Traversal ? Before deleting he parent node, we should delete its child node first. We can therefore use post order traversal as it does the work without storing anything. We can delete three with other traversals…

Question: Given the root pointer to a binary tree, find its size. Input: Sample Tree (Pointer to node 1 is given). Find the size Output: Size = 7 The size of the binary tree is basically the number of nodes in a binary tree. Since, the tree follows a recursive approach we can easily solve this problem by recursion. We calculate the size of left and right sub-tree recursively, add 1 (current node) and return to its parent. The recursive implementation can be done as:- EXPLANATION CASE 1 : When…