Tag Archives: BackTracking

Algorithms involving backtracking

Give an algorithm to find the LCA(Least Common Ancestor) of two nodes in a Binary tree.

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).

Given two binary trees, determine if they are mirror trees.

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

Given a binary tree, find the sum of all its elements.

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… Read More »

Given a binary tree, construct its mirror tree.

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)

Given two binary trees, find if they are structurally identical.

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… Read More »

Give an algorithm to find the height(or depth) of a binary tree.

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… Read More »

Write an algorithm to delete a complete binary tree

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… Read More »

Write an algorithm to find the size of a binary tree.

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… Read More »

Write a program to search an element in a binary tree.

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… Read More »

What is Backtracking?

Backtracking is the method of exhaustive search using divide and conquer. Sometimes the best algorithm for a problem is to try all the possibilities. This is always slow, but there are standard tools that can be used for help. Tools: algorithms for generating basic objects, such as binary strings [2n possibilities for n-bit string], permutations [n!], combinations [n!/r!(n-r)!],… Read More »