Print a Binary Tree in Zig Zag Level Order or spiral order

 Posted on December 27, 2011  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Question: Print a binary tree in zig-zag level order. Zig-zag means print 1st level from left to right, then 2nd level right to left and alternate thereafter. Example: zig-zag level order traversal of below tree will be 0 2 1 3 4 5 6 14 13 12 11 10 9 8 7 Solution1 - Iterative solution Answer: We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal on every alternate level? [Read More]
tree  Binary Tree  BT  kodeknight  recursion  binary-search-tree  BST  iterative  level-order-traversal 

Given a BST, create a mirror of it.

 Posted on May 11, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Change a tree so that the roles of the left and right pointers are swapped at every node. Example So the tree… 4 / \ 2 5 / \ 1 3 is changed to… 4 / \ 5 2 / \ 3 1 The solution is short, but very recursive. As it happens, this can be accomplished without changing the root node pointer, so the return-the-new-root construct is not necessary. [Read More]
tree  kodeknight  mirror  recursion  binary-search-tree  BST  iterative 

GCD and LCM

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Finding the GCD GCD for 60 and 40 is 20: 60 = 40 * 1 + 20 40 = 20 * 2 + 0 LCM for 60 and 40 is 120: 60*40 / 20 Recursive solution for GCD int gcd(a, b): if b==0: return a return gcd(b, a%b) Iterative solution for GCD int gcd(a, b): while (b != 0): //swap a with b, and b with a%b temp = a%b a = b b = t return a Finding the LCM [Read More]
Algorithms  kodeknight  recursion  iterative 

Merge Sort

 Posted on January 14, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Mergesort is one of the older algorithms known since 1945. It is very good example of divide and conquer paradigm and is better than other simpler sort algorithms like selection, insertion or bubble sort. The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. So, merge sort algorithm is a recursive algorithm which calls itself on the smaller problem set. [Read More]
kodeknight  merge  divide and conquer  Data Structures  DS  sorting  incomplete  recursion  programCPP  iterative 

Euclid's Algorithm : GCD of 2 integers

 Posted on January 5, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

The following example solves a classic elementary problem: “Reduce a given fraction to its lowest terms”, e.g. we want to write 2/3, not 4/6. We solve this problem by finding the greatest common divisor (gcd) of the numerator and the denominator by using the famous approach called Euclid’s algorithm. C Code Iterative solution // Iterative algorithm int gcd(int a, int b) { int temp; while(b) { temp = a % b; a = b; b = temp; } return(a); } Recursive solution [Read More]
kodeknight  integer  recursion  iterative  maths