Wednesday, March 7, 2012
Tuesday, September 27, 2011
Evolution in programming Languages
The functional programming is catching up. Java's win over other language came by its developer friendly nature and its adaptation of OOPS paradigm. Following the same path, focusing on Functional Programming few new languages are trying to replace Java and also promise to lower the syntactic noise present in most of programming Languages. Below you can find few links of good write up on a comparison of these languages.
- Digithead's Lab Notebook: Hipster programming languages :
- http://codemonkeyism.com/scala-vs-clojure/
Thursday, September 22, 2011
Printing breadth First Levels of a graph (Or) Tree in python
Today I came across a situation where I had to handle the breadth first levels of a binary tree, each level at once.
Consider the binary tree below,
1
2 3
4 5 6 7
I had to process the nodes level by level,
1
2,3
4,5,6,7
I identified that this problem can be easily solved by considering the tree and DAG ( directed acyclic graph) and performing a bread first search or traversal (BFS) on the tree, starting from the root. But the challenge was BFS, gives me only the path, in this case it would be [ 1,2,3,4,5,6,7]. But this wont be sufficient, I would need to identify the level or depth of each node as I do BFS, so that I can handle the nodes level by level.
Google pointed me to a stackoverflow link http://stackoverflow.com/questions/1894846/printing-bfs-binary-tree-in-level-order-with-specific-formatting , the question exactly matched my situation but unfortunately it did not have any simple or generic solution using bfs. So i decided to write up one on my own, here is the code
Consider the binary tree below,
1
2 3
4 5 6 7
I had to process the nodes level by level,
1
2,3
4,5,6,7
I identified that this problem can be easily solved by considering the tree and DAG ( directed acyclic graph) and performing a bread first search or traversal (BFS) on the tree, starting from the root. But the challenge was BFS, gives me only the path, in this case it would be [ 1,2,3,4,5,6,7]. But this wont be sufficient, I would need to identify the level or depth of each node as I do BFS, so that I can handle the nodes level by level.
Google pointed me to a stackoverflow link http://stackoverflow.com/questions/1894846/printing-bfs-binary-tree-in-level-order-with-specific-formatting , the question exactly matched my situation but unfortunately it did not have any simple or generic solution using bfs. So i decided to write up one on my own, here is the code
This code is also posted in the python recipe of activestate.com
I Came up with another version based on Recursion, which is specific to binary tree. Obviously, this one is very simple than that of its generic graph counter part shown above.
Subscribe to:
Posts (Atom)