BackTracking

What comes to your mind when you think about divide and conquer? Do you think about wars? A strategy? A way you can split up your forces and then conquer the enemy? I am here to tell you that is exactly right. Luckily, in computer science you don’t have to deal with weapons and artillery. There are several ways to approach a problem. Divide and conquer is one of them. In our case a problem statement is our enemy. We need to break it into parts (divide) and then solve…

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 the root pointer to a binary tree, find the LCA (Least Common Ancestor) of two nodes in the tree. Input: Sample Tree (Pointer to node 1 is given). Find LCA of node 5 and 4 Output: Answer = 3 A simple recursive approach can be used to find the LCA (Least common ancestor).

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…