Tag Archives: BackTracking

Algorithms involving backtracking

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)

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 »