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…
Recursion
Algorithms involving recursion


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 substructure 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 substructure, 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, Preorder, Postorder 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 subtree recursively, add 1 (current node) and return to its parent. The recursive implementation can be done as: EXPLANATION CASE 1 : When…

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…

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,…
 1
 2