BackTracking

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 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…

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)!], general strings [k-ary strings of length  n has kn possibilities], etc… Backtracking speeds the exhaustive search by pruning. Example Algorithms of Backtracking Binary Strings: generating all binary strings Generating k-ary Strings. The…