Word Chain Problem.

 Write a program that accepts start and end words and, using words from the dictionary, builds a word chain between them. For added programming fun, return the shortest word chain that solves each puzzle. For example, path from "lead" to "gold" is four steps (lead, load, goad, gold). Turning "ruby" into "code" takes six steps (ruby, rubs, robs, rods, rode, code), while turning "code" into "ruby" (again in six steps).

 Approach:
 let the starting word be "S" and the ending word be "E".
 load the dictionary in a list.
 Put "S" in a Queue.
 parentMap.put("S","null");

 While (!Queue.isEmpty()) {
word "U" = Queue.remove();
if ("U" is visited) then continue;
now starting from "U" do a breadth first traversal, ie, iterate through the dictionary and push all the words "V" which are 1 letter apart from "U" and update their parent as "U". 
parentMap.put("V","U");
if ("V" == "E") { PrintWordChain("V"); }
mark "U" as visited.
}


PrintWordChain("V") {
String T = "";
while ((T = parentMap.get("V")) != null) {
print T;
V = T;
}
}


Dictionary taken as input:
http://www.scrabble.org.au/words/fours.htm


Code input:
LEAD GOLD


Code output:
Max length of word chain: 12
GOLD GELD YELD TELD MELD MEND FEND FEED HEED DEED LEED LEAD 
Length of shortest word chain: 4
GOLD GOAD LOAD LEAD 
Printing all the word chains: 
GOLD GOAD LOAD LEAD 
GOLD GELD YELD TELD MELD MEND FEND FEED HEED DEED LEED LEAD 
GOLD HOLD HILD HIED HAED HEED DEED LEED LEAD 




Code input:
RUBY CODE


Code Output:
Max length of word chain: 11
CODE COTE CITE CETE CATE CARE CAKE CUKE CUBE RUBE RUBY 
Length of shortest word chain: 5
CODE RODE RUDE RUBE RUBY 
Printing all the word chains: 
CODE RODE RUDE RUBE RUBY 
CODE COKE CAKE CUKE CUBE RUBE RUBY 
CODE CORE CIRE CERE CARE CAKE CUKE CUBE RUBE RUBY 
CODE COTE CITE CETE CATE CARE CAKE CUKE CUBE RUBE RUBY 
CODE LODE RODE RUDE RUBE RUBY 
CODE MODE LODE RODE RUDE RUBE RUBY 
CODE BODE MODE LODE RODE RUDE RUBE RUBY 

Print nodes of a BST at a given depth on the same line.

Write code to print out a binary search tree, such that all nodes at a given depth are printed on the same line.

Approach:
This problem is basically asking us to do the breadth First Search of the BST, such that all the nodes at a particular level are printed in new line.


Have a queue data structure.
init by adding root node ie 8 in the queue, then add a marker node which contains "null" elements.
when we dequeue any element from the queue, if its a normal node in the binary search tree then print it and add its not null left & right nodes to queue.
If we get a marker node then print a new line and add it back again to the queue if its not empty.



Code input and output:
int [] A = {8, 3, 10, 1, 6, 14, 4, 7, 13};


Printing inorder recursively: 
1 3 4 6 7 8 10 13 14 
Printing level order traversal of BST: 
8 
3 10 
1 6 14 
4 7 13