<body><script type="text/javascript"> function setAttributeOnload(object, attribute, val) { if(window.addEventListener) { window.addEventListener('load', function(){ object[attribute] = val; }, false); } else { window.attachEvent('onload', function(){ object[attribute] = val; }); } } </script> <div id="navbar-iframe-container"></div> <script type="text/javascript" src="https://apis.google.com/js/plusone.js"></script> <script type="text/javascript"> gapi.load("gapi.iframes:gapi.iframes.style.bubble", function() { if (gapi.iframes && gapi.iframes.getContext) { gapi.iframes.getContext().openChild({ url: 'https://www.blogger.com/navbar.g?targetBlogID\758334277\46blogName\75Sriram\47s+Blog\46publishMode\75PUBLISH_MODE_BLOGSPOT\46navbarType\75BLUE\46layoutType\75CLASSIC\46searchRoot\75http://metallicatony.blogspot.com/search\46blogLocale\75en\46v\0752\46homepageUrl\75http://metallicatony.blogspot.com/\46vt\75-8718433808682107797', where: document.getElementById("navbar-iframe-container"), id: "navbar-iframe" }); } }); </script>

Monday, February 09, 2015

Tweetit - a simple bulk tweeter using twitter APIs and twitter4j

Tweetit is a pretty simple java based command-line bulk tweeter application capable of automatically tweeting, retweeting and cloning existing tweets from twitter stream. Tweetit was primarily created for the ones who work for twitter campaigns fighting for a good cause. This application can be further extended to schedule tweets using readily available scheduler tools that come pre-installed with any operating system. It may also be useful for product marketing and sales announcements using a trending hashtag to get maximum reach.

I’m thankful to twitter4j and twitter APIs without which Tweetit could not have been created. Tweetit has been open sourced under Apache 2.0 license and hosted in github. Feel free to download the source from GitHub repository - Tweetit and play around.

Origin of Tweetit
        A super frustrated group of good-hearted people lost their patience waiting for the American government to finalize and publish a rule RIN:1615-AB92, also called H4EAD – a provision to provide work authorization for certain H4 spouses who have been backlogged heavily due to the unavailability of immigrant visas (green cards). They have been waiting for this rule to effect since 2012. Out of extreme frustration, this group made a decision in trackitt discussion thread to start running campaigns through various mediums. There were some from the community that sent emails to their local congress men, there were some who wrote post cards to USCIS office in Washington DC, there were some who sent fax to DHS and USCIS, there were some who started aggressive tweeting and finally there were some who met with USCIS directors & law offices to get updates and represent the whole community. The members of this community were separated by distance but unified by their thoughts and actions.

Out of all such campaigns, twitter campaign picked up a lot of steam after USCIS director Leon Rodriguez stated that he understands their frustrations and knows about the tweets and emails that are being sent. He further recommended to keep the momentum and noise high to get things done sooner. After listening to his suggestions, this community started working more towards their campaigns in which twitter became the primary medium of expression. This created a need for a simple bulk tweeting application that will help everyone to work more towards this good cause.

Capabilities
Tweetit is capable of
  • Searching tweets under a specific hashtag from twitter stream and retweeting them back in your timeline
  • Searching tweets under a specific hashtag from twitter stream, cloning the searched tweets and tweet them to your timeline as new tweets. I call this cloning!!
  • Tweeting status messages and pictures that can be picked from a source of data, currently being a spreadsheet. The pictures need not be embedded in the spreadsheet but just an absolute path (reference) to pictures in your hard drive has to go in the spreadsheet

Being Ethical
        Twitter is a wonderful social medium through which voices of unheard and unseen can be listened to. Social media listening tools monitor and measure trends of tweets to learn and aid organizations to make informed decisions. Campaigns take place in twitter to express support and hate, likes and dislikes, agreements and disagreements to spread the cause, news and views. Therefore, it is not right to spam such a useful social medium and disrupt the system. It is indeed not ethical to do it.

Twitter officially encourages everyone to build tools and applications over the features it provides. However it throttles the traffic based on various measures so that a higher volume traffic source does not choke a lower volume traffic source. Twitter allows a maximum of 2400 updates (includes tweet and retweet) per day and it further breaks down the limits per 15 minute window - https://support.twitter.com/articles/15364-twitter-limits-api-updates-and-following. Some of the known throttling mechanisms that twitter already uses are IP based and APIs based. It has quotas per API per application. Users that are often flagged and suspicious are moved to a lower tier or sometimes even blocked permanently.

Tweetit application has been built completely being conscious about these principles. It neither tries to spam nor encourages you to do so. It has been built with just one good objective - to ease the life of twitter-heavy users that mainly run good-cause campaigns. It accomplishes this by pausing a minimum of 10 seconds in between tweets & retweets. Apparently, generous users can increase the interval between tweets but cannot bring it lower than the minimum allowed. This helps users two folds
  • To be a good twitter user paving way for rest of the world to work for their respective needs and causes
  • Do not fall under twitter’s radar-of-scrutiny and take the brunt of being labelled as a flagged-user

Tweetit Prerequisites
  • Tweetit runs in any operating system that supports Java run time environment (>= version 1.6). Tweetit is not a web application and can be just run from the command-line or shell prompt using its executable jar file.
  • Supports tweeting text and images. Currently it supports only JPEG (.jpg) images.
  • It is not required to have Microsoft Office (or any other ports of it) installed but it will be good to have, if you would like to add and edit the contents of spreadsheet. Please note that Tweetit supports (.xls) spreadsheets but currently does NOT have the support for newer (.xlsx) spreadsheets yet.
  • And lastly, if you have a basic technical ground or has a very basic exposure to java, it is pretty easy to catch up the rest of instructions and use this app

Tweetit will NOT need your Sign-in password but needs your OAuth keys to tweet on your behalf. It uses a special file called key file. This key file is expected to contain the user’s OAuth keys for twitter authentication. These keys can be generated at https://apps.twitter.com. OAuth keys are a secured way to access and post tweets on your behalf. Below steps will guide you to generate needed keys and access tokens. It's pretty simple to do and it will not take more than 15 minutes. Once created, these OAuth keys can be used forever to run tweetit. It is just an one time effort. Please note that, you will have the full control over your keys and contents of tweets. Tweetit does not and cannot misuse your keys. Neither it can snoop or mess with your tweet contents.

Generate OAuth keys
OAuth is a pretty widely used Open source authorization standard that any client application can use to get secure access to users resources without the need of their login credentials. Below is a onetime setup steps that has to be followed to generate OAuth keys from your twitter account. Once done, these keys can be used to run “tweetit”.

1) Go to https://twitter.com/settings/devices and add your phone number. Twitter validates your phone number by sending a verification code. Once done, UNTICK all the check boxes unless you want to receive twitter text notifications to your mobile. Kindly be aware that twitter does not allow you to generate OAuth keys if you do not have a phone number added to your profile. A screenshot that shows all text related settings of mobile deselected.



2) Go to https://apps.twitter.com/ and create a new application through which you can create keys. Please note that the application name should be globally unique. Click “Create your Twitter application” after accepting the Developer agreement. Below is a screen capture of the details after having entered.



3) Once your application is successfully created, navigate to “Permissions” tab/link and provide “read and write” permission as shown below. This ensures that your keys can be used by Tweetit to post tweets on your behalf.



4) Click “Keys and access tokens” tab/link to display application settings including your consumer key and consumer secret. Scroll down to “Your Access token” and click “Create my Access Token” to create access tokens.



5) Now you got all the OAuth keys and access tokens that are needed. The values you just got for a) Consumer Key b) Consumer Secret c) Access Token and d) Access Secret
need to be copied to a text file called keyfile.txt as shown below. A sample keyfile.txt can be downloaded from github repository https://github.com/metallicatony/tweetit/blob/master/src/main/resources/keyfile.txt. If you find that the contents of the downloaded keyfile are all present in the same line, it is because of End of line conversion differences between unix and windows. Kindly make the file look like the below screenshot as a first step. Then replace the respective values of keys and tokens generated from the previous step, in place of dummy values marked as ABCD, EFGH, IJKL and MNOP of the downloaded keyfile.



Download other needed resources
Below is a list of steps that need to be followed to have all the needed resources in place before running “tweetit”. Please note that all resources are hosted in github.
  • Create a directory called C:\tweetit and move the above created “keyfile.txt” there if not done before. Though you have a choice to place the keyfile.txt anywhere in your harddrive and refer the full path while running “tweetit”, it is prudent to place it under C:\tweetit\

  • Download tweetit jar application and save in the same directory location. The jar can be found here https://github.com/metallicatony/tweetit/blob/master/target/tweetit-1.1.jar?raw=true

  • As said before, tweetit picks the contents for your tweets from a spreadsheet (*.xls). The spreadsheet (.xls) should have the message content of your tweets and optionally it can contain the path to the images in your computer that you want to upload as part of your tweet. Please download a template of the spreadsheet from the repository https://github.com/metallicatony/tweetit/blob/master/src/main/resources/tweets.xls?raw=true and place it under C:\tweetit\

  • Download a sample picture https://github.com/metallicatony/tweetit/blob/master/src/main/resources/H4EAD_Banner_Woman.png along with the above spreadsheet and save it under the same directory C:\tweetit\

  • This has been already covered by the last step from the previous section. Double check whether you already got keyfile.txt after merging in your keys and tokens into it. This keyfile needs to go under the same directory C:\tweetit\
  • .
After the above steps are complete, you are now ready to bulk tweet using “tweetit”.

Tweetit Commands
Below are some sample commands that you can use from a windows command prompt to run tweetit. The same set of commands can be used if you are using from Linux or any unix variant operating systems too. The only change will be the referred absolute path in the command. Before you try out below commands, please navigate to tweetit’s home directory C:\tweetit\

Search & Retweet
The below command pulls a recent 250 tweets with hashtag #H4EAD and retweets the same. Kindly note that by default tweetit retweets the latest 500 tweets. The retweets are done every ~12 seconds
java -jar tweetit-1.1.jar --retweet --keyfile "C:\tweetit\keyfile.txt" --search "#H4EAD" --count 250 --every 12 

A screenshot of the above command in action



Clone Tweets
The below command pulls a recent 250 tweets with hashtag #H4EAD ,clones them and tweets them as new tweets to your timeline. Kindly note that by default tweetit pulls the latest 500 tweets but the tweets are done every ~12 seconds.
java -jar tweetit-1.1.jar --clone --keyfile "C:\tweetit\keyfile.txt"

A screenshot of the above command in action



Tweet using Spreadsheet contents
The below command pulls the contents of the spreadsheet that you downloaded and tweets them to your timeline. The path to the spreadsheet can be explicitly mentioned as below. If not, it assumes a default path C:\tweetit\tweets.xls
java -jar tweetit-1.1.jar --tweet --keyfile "C:\tweetit\keyfile.txt" --every 10 --spreadsheet "C:\tweetit\tweets.xls"

A screenshot of the above command in action



Tweetit is really helpful when you want to tweet and retweet bulk on a daily basis. It can save you a lot of time by automatically tweeting with a simple run of a command and thereby you can focus on your day to day activities without much intervention.

Wednesday, December 31, 2014

CRUD REST APIs using Java, MongoDB, Spring, Spring Data, Apache CXF, Maven and SLF4J

This project shows how to build a web application and perform basic CRUD operations using MongoDB as the datastore. It exposes the built operations as REST web services or APIs too. I created this primarily to show how to incorporate and kickstart MongoDB in web applications. And hence this post focuses more on MongoDB than anything else. I would recommend referring my previous posts if you would like to know the basics of building a web app CRUD REST & SOAP Services using Java and Apache CXF.

The following were used to build this project
1) Java 1.6
2) Spring Tool suite (STS) 3.1.0
3) Spring framework 4.0.0
4) Spring Data 1.6.1
5) Apache CXF 2.7.5
6) Apache maven 3.0.4
7) Log4j 1.2.16 and Slf4j 1.6.1
8) Jackson 1.9.0
9) SOAP UI 4.5.1
10) MongoDB 2.6.4

Objective
The objective of this project is to demonstrate a simple CRUD operation on a set of employee information in MongoDB. All the CRUD operations are exposed as REST webservices and so they can be invoked through any type of web client like SOAPUI or even using a simple web browser.

About MongoDB
Mongo DB is one of the most popular NoSQL database that persists information as JSON-style documents without enforcing a schema or a defined structure. This type of storage and retrieval is very helpful in types of applications where speed, performance and scaling overweigh data redundancy. The best documentation I have found so far is Mongo’s own official manual MongoDB Official Manual.

Install & configure MongoDB
Before proceeding to build the web app, it is required to install and configure MongoDB by following MongoDB Official Installation Instructions . A basic level of understanding about mongo concepts and commands are needed (MongoDB official CRUD operations) before proceeding further.
The next few steps are needed to prep MongoDB before proceeding to build the webapp. After installing MongoDB, let’s make MongoDB to NOT allow anonymous logins. And that's how a typical installation will be in an enterprise. This needs Mongo daemon/server to be started in “auth” mode. But before starting in "auth" mode, we need to create an administrator user.

1) Create administrator user via mongo console
> db.createUser({user: "administrator", pwd: "password", roles: [ {role: "userAdminAnyDatabase", db: "admin"}]});
Successfully added user: {
        "user" : "administrator",
        "roles" : [
                {
                        "role" : "userAdminAnyDatabase",
                        "db" : "admin"
                }
        ]
}

2) Create one more non-admin/regular user who has RW permission for all databases in MongoDB
> db.createUser({user: "metallicatony", pwd: "password", roles: [{role: "readWriteAnyDatabase", db:"admin"}]});
Successfully added user: {
        "user" : "metallicatony",
        "roles" : [
                {
                        "role" : "readWriteAnyDatabase",
                        "db" : "admin"
                }
        ]
}

3) Start Mongo daemon in “auth” mode
 C:\Program Files\MongoDB 2.6 Standard\bin> mongod.exe --auth --dbpath "C:\Program Files\MongoDB 2.6 Standard\data\db" 

4) Test whether Mongo allows anonymous operations. It won’t.
> show dbs
2014-12-30T10:08:17.669-0800 listDatabases failed:{
        "ok" : 0,
        "errmsg" : "not authorized on admin to execute command { listDatabases: 1.0 }",
        "code" : 13
} at src/mongo/shell/mongo.js:47

5) Authenticate with the non-admin user created in step 2)
> db.auth("metallicatony", "password");
1

6) Database “organization” and collection “employees” are something that will be used in our webapp. Switch to database “organization” and insert a new document in a collection called “employees”.
> use organization;
switched to db organization


> db.employees.insert({empId: 1, fname: "Richard", lname: "Stallman", deptName: "CS", salary: 5000});
WriteResult({ "nInserted" : 1 })


> db.employees.find();
{ "_id" : ObjectId("54a32c39961019d59eacd4ce"), "empId" : 1, "fname" : "Richard", "lname" : "Stallman", 
 "deptName" : "CS", "salary" : 5000 }

> db.sequence.insert({empId: 1});
WriteResult({ "nInserted" : 1 })

With that done, the installation and prep work of mongodb is complete. The next steps focus on building the web application that will interact with MongoDB. This basic web application will have the CRUD capabilities - create, read, update and delete employees from mongodb.

POM Changes
Spring Data is the backbone for all the interactions that are performed between the web application and the MongoDB. Spring data provides a consistent programming model and lets java programmers to use all the features of MongoDB using a repository style data access layer. To include spring data for mongodb as part of the project, the following additions are made to the application’s pom.

Add the version of spring data mongodb in the pom properties
1.6.1.RELEASE
Add the dependency under pom dependencies

  org.springframework.data
  spring-data-mongodb
  ${spring.data.mongo.version}


MongoDB connection properties & Application context configuration
The connection properties of MongoDB are stored in a file called "database.properties" and resolved when spring loads "applicationContext.xml" file.
  mongo.hostname=localhost
  mongo.port=27017
  mongo.username=metallicatony
  mongo.password=password
  mongo.databaseName=organization
The below property placeholder configuration from applicationContext.xml file loads the properties

Added to that, below are the bean definitions in applicationContext.xml file to instantiate a "mongoTemplate" that will be injected into Spring repository. The web application interacts with the Mongo layer using the repository.


 
 

 


    
    




 
 
 

Web application descriptor's (web.xml) context config location parameter points to the xml files that contain bean definitions. In our application, it points to both cxf-bean.xml and applicationContext.xml files. Below is a snippet from web.xml

  contextConfigLocation
    
     classpath*:cxf-bean.xml,
     classpath*:applicationContext.xml
    


Application Code Layers
The web app code is organized into 7 layers wherein every layer corresponds to a package. The layers are
  • Service Layer - contains the interface and implementation of the APIs exposed 
  • Request Layer - contains the API request entities 
  • Response Layer - contains the API response entities 
  • Adapter Layer - contains helper methods that can convert entity of one type to other 
  • Business Layer - lies in between service and repository layer and applies any business logics if any 
  • Domain Layer - contains domain entities, more specifically for this project, it comprises entities that represent mongo documents 
  • Repository Layer - the layer down in the stack that bundles all the mongo queries to perform the desired operation in mongo database 

Repository & Domain Layers
The layers other than repository and domain layers are pretty much self-learnable from the code. Moreover the code follows a similar pattern like that was discussed in the previous posts about building CRUD REST and SOAP APIs and building CRUD operations using Spring and Hibernate. The domain layer contains two entities - Employee and Sequence. The employee entity is the one that maps to any document in "employees" collection that was created in step 6. This is done by using @Document annotation. This is more similar to mapping an entity to a table record in a database table.
@Document(collection="employees")
Sequence entity maps to a special counters collection called "sequence". Every employee id is an auto incremented sequence number that is generated during run time. More about this can be read from mongo's official manual Creating auto incrementing sequence number . In our case, the helper method "getNextId()" handles the job of fetching the sequence document and returning the incremented sequence number like this
 /**
  * Gets the next sequence id
  * @return the sequence id
  */
 public Long getNextId() {
  // Get object id of the sequence document
  Query queryGet = new Query(Criteria.where("empId").exists(true));
  Sequence sequenceDocGet = mongoTemplate.findOne(queryGet, Sequence.class);
  log.info("objectId={}", sequenceDocGet.get_id());
  
  // Increment emp id of the document fetched above and return the new sequence number
  Sequence sequenceDoc = null;
  Update update = new Update();
  update.inc("empId", 1);
  Query query = new Query(Criteria.where("_id").is(new ObjectId(sequenceDocGet.get_id())));
  FindAndModifyOptions options = new FindAndModifyOptions();
  options.returnNew(true);
  sequenceDoc = mongoTemplate.findAndModify(query, update, options, Sequence.class);
  if (sequenceDoc != null) {
   return sequenceDoc.getEmpId();
  }
  return null;
 }
The code for repository layer resides in EmployeeRepository class. All the mongo specific operations are possible from this layer by spring injecting mongo template
@Autowired
private MongoTemplate mongoTemplate;
The repository layer comprises operations to
  • find all employees (this operation is exposed as REST API - HTTP GET /employees)
  • find all employees by last name (this operation is exposed as REST API - HTTP GET /employees?lname="name")
  • find employee by employee id (this operation is exposed as REST API - HTTP GET /employees/{empId})
  • create employee (this operation is exposed as REST API - HTTP POST /employees)
  • update employee (this operation is exposed as REST API - HTTP PUT /employees/{empId})
  • delete employee (this operation is exposed as REST API - HTTP DELETE /employees/{empId})
Most part of the code involved in performing the above operations is about creating the right Mongo Query and running it using the injected mongo template. Being comfortable with basic mongo query syntax will help a lot here. Feel free to download, build and browse through the code from my GitHub repository - CRUD APIs using Mongo.

Labels: ,

Thursday, June 26, 2014

A playful approach to tackle programming questions ("Phone words using dialpad" problem)

Programming questions are always tricky. It often makes you dazed and confused. Any software engineer interview for a programming position involves a couple of programming questions. After listening to a question from the interviewer, when you try to answer back and that's when you go erratic. That's pretty normal for everyone and there is no need to be worried and concerned. The objective of this post is to show a way to tackle such programming questions. It will illustrate a planned approach that you might want to tread on for easily arriving at solutions. I have taken a famous problem called "Phone words" to explain this approach.

“Phone words” is a programming question that features in many interviews to test the analytic skills of a programmer. The problem statement goes like this: You are given a 7 or 10 digit phone number. In every telephone or a cell phone, we have numbers ranging from 0 to 9 in the dial pad. Every digit in the dial pad has either 0 or 3 or 4 letters mapped for every digit. For the given phone number you need to find out all combinations of words that is possible using the letters of every digit of the phone number.

I couldn’t find a clean solution for this question anywhere and so wanted to post my solution along with the approach taken. Be it any programming question, if you work to find a solution without doing any ground work, it is not going to help at all. A step by step systematic approach is what will help you find a solution. It’s a skill to learn and acquire but an art to conquer!!

Programming problems can be addressed in the same way you prepare yourself to play a new computer game. Say, suppose you heard about a new game from a game-maniac friend of yours. He is in all praises for this game. And now, after listening to all those good stories from him, you are very desperate to play this game. You are restless. You wait with no patience for the day to arrive so that you can play this wonderful game. Imagine how you prepare yourself to play a computer game, a game that you have never played in the past. Imagine how excited you will be, sitting right before the screen waiting for the game to load. Once your game starts, your curious playful mind will begin to find out answers for the following questions

1. What exactly is the objective or mission of this game?
2. What are the aids and powers that I’m provided with as a player? Do I carry health tabs, armory, high-tech weapons?
3. Is there any specific learning or understanding that I need to do about my given aids and powers?
4. Can I play this game for the first few times just to familiarize myself without being mindful about my mission, without worrying about whether I’m winning or losing?
5. After I get a sense that I’m comfortable playing this new game, I have to think and plan a little bit around those deadly traps and devilishly humongous demons with whom I want to deal carefully. What is the appropriate time to use my powers so that they can be put to best use?
6. And finally, I will try to frame a strategy to tackle all my enemies so that I can effectively accomplish the mission of the game

That’s how you plan before playing a game, isn’t it? This exactly is the thought process that is needed to solve a programming problem. Once we are able to figure out answers for the above questions, it is going to be much easier to solve the actual problem. Let us follow the above steps and figure out how helpful they are in solving our “Phone words” problem.

What is the mission of this game?
The objective of the problem is to find out all possible words that could be created out of the given numbers. This is a classic example of a permutation and combination problem.

What are the aids and powers that I’m provided with as a player?
I’m given a set of numbers that represents a phone number and a phone dial pad that has numbers running through 0 to 9. Every number is mapped to a set of characters. Any one of those characters from every digit will be considered every time I try to create a possible word

Is there any specific learning that I need to perform about the aids and powers that I’m given with?
As a player, I’m provided with a phone dial pad and a set of numbers for which I need to create possible words. When I look at the dial pad, I see that not all numbers have the same 3 characters associated with them. It appears that there can be zero or more letters for a number. Digits like 0 and 1 don’t have any letters while digits 7 and 9 are mapped to 4 characters each. Wow, that’s a good point to understand before trying to solve the problem!

Can I play this game for the first few times just to familiarize myself without being mindful about my mission and without worrying about whether I’m winning or losing?
I want to play this game for a couple of times so that I can familiarize myself. I will be happy to choose the least difficult level so that it buys me more time on stage. Likewise, when a programming problem is given, it’s important to run through the problem with a couple of easy experiments. In this case, say for example, running through the problem using an imaginary phone number “23” will make me understand that the possible words are “AD”, “AE”, “AF”, “BD”, “BE”, “BF”, “CD”, “CE”, “CF”. Running through this exercise and illustrating the samples increases the confidence.

Can I think and plan a little bit around those deadly traps and devilishly humongous demons with whom I want to deal carefully?
When i'm playing a game, as soon as I spot some deadly traps, I want to think and plan a bit about them. I want to understand so that i can better tackle those traps. Likewise, there are a couple of traps in this problem. The numbers 0 or 1 do not have any characters associated with them. And there are numbers 7 and 9 that are mapped to 4 characters each, which is 1 character more than the typical 3 characters per number. This in turn means that a pure iterative solution might fail if it goes by the assumption that it is always 3 mapped characters per digit across board. I have to be careful about it. In case of 0 or 1, it will be the digits 0 and 1 used for creating a word and when it is 7 or 9, I must be careful to use all the 4 characters to create words. To re-familiarize myself, I need to run through those traps a couple of times to improve my understanding. Say, I’m now given with an imaginary number “702”. Then the possible word combinations will be “P0A”, “P0B”, “P0C”, “Q0A”, “Q0B”, “Q0C”, “R0A”, “R0B”, “R0C”, “S0A”, “S0B”, “S0C”.

Can i frame a strategy to tackle all the enemies so that i can accomplish the mission of the game?
Now comes the big part. I know quite a bit about the game now. I know about the powers that I’m given with, I know where to hunt for gold and I’m aware of the exact place and point at which those devils will show up. Now, it’s time for me to craft a plan, a plan that will defend me and defy all my enemies. Thinking at a very high level, there are two ways I can solve this problem.

Iterative Solution:
Let’s say I’m given with an imaginary phone number 234 ({abc}, {def}, {ghi}). Then as a first step, i have to think about the number of possible words that can be created out of that phone number. It will be 3x3x3 = 27 words.

Let me run through this solution in my mind. As the first digit of the given phone number is 2, I can have the letters - a, b and c stashed separately. Once I see the second digit 3, I can append every mapped character of 3 to the previously stashed words. Now the stashed words become ad, bd, cd and ae, be, ce and af, bf, cf. The next digit is 4 and so the stashed words will now become – adg, bdg, cdg, aeg, beg, ceg, afg, bfg, cfg, adh, bdh, cdh, aeh, beh, ceh, afh, bfh, cfh, adi, bdi, cdi, aei, bei, cei, afi, bfi, cfi. Running through this gives me a clue that this is an iterative solution. Additionally I need two lists, one with the stashed words and the other list for retaining the new words that are created by appending the stashed words with the letter that I’m iterating with. After appending all letters mapped for a digit with the stashed words, the new list becomes the stashed list after which the new list is emptied to ready for the next iteration. Simple, isn’t it?

/**
 * Returns the list of words created using phone dial pad and the given phone number
 * @param digits the phone number
 * @return list of combination of words
 */
public static ArrayList<String> getWordFromDialPad(String digits) {
  ArrayList<String> res = new ArrayList<String>();
  ArrayList<String> preres = new ArrayList<String>();
  res.add("");

  for (int i = 0; i < digits.length(); i++) {
   for (String str : res) {
    String letters = map.get(digits.charAt(i));
    for (int j = 0; j < letters.length(); j++)
     preres.add(str + letters.charAt(j));
   }
   res = preres;
   preres = new ArrayList<String>();
  }
  return res;
 }

This iterative solution looks simple but the only drawback is it needs more space to stash the list of words for every iteration. The complete implementation can be accessed from my GitHub repository - Phone words iterative solution.

Recursive Solution:
This is another solution for the same problem. In fact, this solution is a blend of recursive and iterative. The best part of this solution is that it just needs a single array equal to the size of the phone number!! Awesome isn’t it? No more extra space is needed!! Recursive solutions are interesting to understand and efficient most of the times. Instead of thinking iteratively, recursion will make you think differently. It wants you to go deep down and loop through all possible combinations in the lowest possible levels and then slowly climb upper levels to repeat the same. And that’s exactly this recursive method does
/**
 * Recursive helper method to create a word from dial pad
 * @param word character array
 * @param numbers given input numbers as string
 * @param start the index of input digit that is being processed
 */
private static void getWordFromDialPad(char[] word, String numbers, int start) {
  // base case -> start is the index value of the position from the word
  if (start > (numbers.length() - 1)) {
    System.out.println(++counter + " ==> " + new String(word));
    // look up dictionary to find whether the word is meaningful or not
    return;
  }

  // Identify the number of iterations based on the digit
  Integer number = numbers.charAt(start) - '0';
  int iterations = getSizeOfFirstDimension(number);


  // Iteration in a recursive method is equal to number of possible chars a digit can take
  // for eg. digit 2 can take 3 possible chars - A, B and C where as digit 7 can take 4 different chars
  for (int j = 0; j < iterations; j++) {
    // store a possible character for the digit and move on to the next position by 
    // calling the recursive method again
    word[start] = getCharacterFromDialPad(number, j);
    getWordFromDialPad(word, numbers, start + 1);
  }
}

That’s the core part of this recursive solution. The rest of the implementation has helper methods to support the above recursion. The complete implementation can be accessed from my GitHub repository - Phone words recursive solution.

A preface of any book will brief and summarize about what the book is about. Likewise it is very important to understand the preface of a programming problem by asking the above questions. It is very similar to the set of questions that you ask yourselves when you get ready to play a new game. Running through a couple of simple experiments will give deeper understanding and confidence. It will stand as a stepping stone to craft the final solution!!

Labels: , ,

Wednesday, April 30, 2014

Generic Stack and Queue using Linked List and resizing Array

Stacks and Queues are one of the most basic and important data structures widely used in computer science. Understanding the operational semantics of these data structures will reward anyone. Going a step ahead and understanding the inner workings of these structures will lighten with much more knowledge. Once the mechanics of these data structures are well understood, trying to build a custom one using other foundational data structures will be a challenge. Leaping one more step ahead to build a generic version of stack and queue using the same foundational structures will not be a very easy task to do, but if you do, it sure will adorn your cerebral cortex.

This post focusses on building a generic stack and queue using two foundational structures - linked list and array. So there are going to be 4 different types of implementation.
1) Build a stack using Linked List
2) Build a stack using resizing array
3) Build a queue using Linked list
4) Build a queue using resizing array

Generic Datastructure
Stack is a LIFO data structure and Queue is a FIFO data structure. To understand more about these, I would recommend to google. A generic data structure is more like a container for any type of java object. The data structure should not depend on the type of object that one needs to use with it. The object can be anything. It is not a healthy practice to build a data structure for every type of object that you want to use with it.

The semantics of a linked list is different from an array because linked list allows accessing any element traversing from the first element while an array allows random access based on the index of the element. Underlying rules like these, pose a challenge for a developer to construct a stack or queue using the foundational structures.

The below illustrated "isEmpty" and "iterator" methods are common for both Stacks and queues. As the name illustrates, isEmpty tells whether the structure is empty and the iterator method returns an iterator to run through the elements. The beauty is that a user does not need to understand the underlying data structure if he has to iterate through the elements.

Following is the code snippet for all the above mentioned data structures. Most part of the code is not that difficult to understand though I have some inline comments wherever I felt some explanation is necessary.

Stack using Linked List
A single linked list always has a series of elements chained together. Every element has data and a reference to the next element. The first element is called head and the last element in the chain is called tail. That in turn does not mean all the data structures that are built using linked list need to have 2 references internally maintained for head and tail. It is totally up to the data structure that is built out of linked list. Take for example, the stack needs to internally preserve just one reference which is "head", so that it can perform its day to day work. This is because both operations “push” and “pop” that are exposed from a stack happens from the top aka head element. Push adds a new element at the head and pop returns and removes the element at the head of the linked list.

/**
  * Returns true or false based on whether the stack is empty or not
  * @return boolean
  */
 public boolean isEmpty() {
  return (null == head);
 }

/**
  * Push data to stack
  * @param data
  * @return true if push was successful else false
  */
 public boolean push(T data) {
  if (null != data) {
   Element prevHead = head;
   head = new Element();
   head.data = data;
   head.next = prevHead;
   return true;
  } else {
   return false;
  }
 }
 
 /**
  * Pops data from stack
  * @return data if pop was successful else null
  */
 public T pop() {
  if (!isEmpty()) {
   T data = head.data;
   head = head.next;
   return data;
  } else {
   return null;
  }
 }

The following iterator helps to run through the elements in the stack
@Override
 public Iterator<T> iterator() {
  return new Iterator<T>() {
   
   private Element current = head;

   @Override
   public boolean hasNext() {
    return current != null;
   }

   @Override
   public T next() {
    final T data = current.data;
    current = current.next;
    return data;
   }

   @Override
   public void remove() {
   }
  };
}

Here is the github link to the code for Stack built using Linked List - Github - Stack using Linked List

Stack using resizing Array
Stack using array might look simple at the first sight. However, it is definitely not if you are implementing a self-resizing array. A self-resizing array is the one that can modify its size based on the usage. This ensures an optimum usage of memory based on the number of elements in the stack.

Push operation always happens at the end of the array. It is not a good idea to add the new element at the first index because a stack is a FIFO data structure. The new element needs to be added to the end of array and the actual number of elements in the stack is maintained internally in a variable. The stack needs to be resized to twice its capacity if it was found to be already full. This in turn means that for N elements added to the stack, the array needs to be resized logarithmic times.

 /**
  * Returns true if the stack is empty
  * @return
  */
 public boolean isEmpty() {
  return (n == 0);
 }

/**
  * Pushes object to stack. Resizes if needed.
  * Note that resize operation happens before push.
  * @param data
  * @return
  */
 public boolean push(T data) {
  if (null != data) {
   if (n == list.length) {
    resize(list.length * 2);
   }
   list[n++] = data;
   return true;
  } else {
   return false;
  }
 }

 /**
  * Resizes the existing stack by creating a new stack
  * and copying all the elements from existing stack.
  * 
  * In case of a growing stack, the source of data is small
  * In case of a shrinking stack, the new target is small
  * And so the copying operation has been restricted to number of elements
  * 
  * @param capacity
  */
 private void resize(int capacity) {
  T[] newlist = (T[]) new Object[capacity];
  for (int i = 0; i < n; i++) {
   newlist[i] = list[i];
  }
  list = newlist;
 }

Pop operation always happens from the last element as that is the most recently added element to the stack. After a pop is complete, the stack is resized to a half of its capacity if the utilization is found to be quarter or less than the current capacity.

 /**
  * Pops out from stack. Resizes if needed.
  * Note that resize operation happens after pop.
  * @return
  */
 public T pop() {
  if (!isEmpty()) {
   T data = list[--n];
   list[n] = null;
   if (n <= list.length/4 && n > 0) {
    // resize the stack if the utilization is lesser than or equal to quarter of the capacity
    // not needed to resize if number of elements in stack was 1 and that element was popped (the new n will be 0 then)
    resize(list.length/2);
   }
   return data;
  } else {
   return null;
  }
 }

The following iterator helps to run through the elements in the stack
 @Override
 public Iterator<T> iterator() {
  return new Iterator<T>() {
   // as array data structure stores in the order of push but stack is a LIFO data structure
   // the iterator runs reverse
   private int i = (n-1);
   
   @Override
   public boolean hasNext() {
    return (i >= 0);
   }
   
   @Override
   public T next() {
    return list[i--];
   }

   @Override
   public void remove() {
    
   }
  };
 }

Here is the github link to the code for Stack built using Array - Github - Stack using Resizing Array

Queue using Linked List
Queues using linked list needs two references – "head" pointing to the first element of the queue and "tail" pointing to the last element of the queue. Enqueue adds an element to the end of the queue and dequeue returns and removes an element from the start of the queue.

The enqueue operation has a special case when the first element is added to an empty queue. When the queue has just one element, both head and tail need to point to the same element which will be the first element in the queue.

/**
  * Returns true or false based on whether the queue is empty or not
  * @return boolean
  */
 public boolean isEmpty() {
  return (null == head);
 }

/**
  * Enqueues or adds the element to the end of queue
  * If the queue is empty before enqueue, the head and tail of the queue will point to the new element enqueued
  * @param data
  * @return true if enqueue was successful else false
  */
 public boolean enqueue(T data) {
  if (data != null) {
   Element prevTail = tail;
   tail = new Element();
   tail.data = data;
   tail.next = null;
   if (isEmpty()) {
    head = tail;
   } else {
    prevTail.next = tail;
   }
   return true;
  } else {
   return false;
  }
 }
Dequeue has a special case as well. When the queue becomes empty after the last element is dequeued, the head and tail references should point to null.
/**
  * Dequeues element from the start of the queue and returns the element's data. Returns null if there are no elements in queue.
  * If the queue is empty after a successful dequeue, head and tail will be reset to null
  * @return
  */
 public T dequeue() {
  if (!isEmpty()) {
   T data = head.data;
   head = head.next;
   if (isEmpty()) {
    tail = head;
   }
   return data;
  }
  return null;
 }

The iterator is simple for a queue built using linked list. It has to run from the first element to the end.
@Override
 public Iterator<T> iterator() {
  return new Iterator<T>() {
   
   private Element current = head;

   @Override
   public boolean hasNext() {
    return current != null;
   }

   @Override
   public T next() {
    final T data = current.data;
    current = current.next;
    return data;
   }

   @Override
   public void remove() {
    
   }
  };
 }

Here is the github link to the code for Queue built using Linked List - Github - Queue using Linked List

Queue using resizing Array
Queue using array is possible using two indexes – headIndex and a tailIndex. headIndex points to the first valid element in the queue. Remember a dequeue operation removes the element from the head. So a dequeue operation can leave "holes" in the queue. tailIndex points to the last valid element in the queue. This in turn means that the length of the queue will be the tailIndex value. Not to forget that the underlying array has to be resized for an optimal usage of memory.
A push operation happens at the tailIndex. If the queue is full, the capacity is resized to twice

 /**
  * Returns true if queue is empty
  * @return
  */
 public boolean isEmpty() {
  return (0 == tailIndex);
 }

/**
  * Enqueues to queue, resizes if needed
  * @param data
  * @return
  */
 public boolean enqueue(T data) {
  if (data != null) {
   if (!isEmpty()) {
    // queue is full
    if ((tailIndex - headIndex) == list.length) {
     resize(2*list.length);
    }
   }
   // if the queue is empty or if the queue is not full
   list[tailIndex++] = data;
   return true;
  } else {
   return false;
  }
 }


 /**
  * Resizes the queue to the provided capacity
  * @param capacity
  */
 private void resize(int capacity) {
  T[] newlist = (T[]) new Object[capacity];
  int i = headIndex;
  int j = 0;
  for (; i < tailIndex; i++, j++) {
   newlist[j] = list[i];
  }
  headIndex = 0;
  tailIndex = j;
  list = newlist;
 }


A pop operation pops an element from the head of the queue. After the operation, if the utilization of the queue is found to be quarter the capacity or lesser, then the current capacity is resized to half. The queue need not be resized if the length of the queue is already 1. It is ok to have a space readily available for the first element of the queue.
/**
  * Dequeues from queue, resizes if needed
  * @return
  */
 public T dequeue() {
  if (!isEmpty()) {
   T data = list[headIndex];
   list[headIndex++] = null;
   if ( ((tailIndex - headIndex) <= list.length/4) && list.length > 1) {
    // resize the queue to half it's capacity, if the utilization is lesser than or equal to quarter of the capacity
    // do not resize if number of elements in queue was 1 and that element was dequeued (the new number of elements will be 0 then)
    resize(list.length/2);
   }
   return data;
  } else {
   return null;
  }
 }



The iterator for a queue built using array is not difficult as the iteration has to run from the element at headIndex to tailIndex.
@Override
 public Iterator<T> iterator() {
  return new Iterator<T>() {
   
   private int i = headIndex;
   
   @Override
   public boolean hasNext() {
    return (i < (tailIndex - headIndex));
   }

   @Override
   public T next() {
    return list[i++];
   }

   @Override
   public void remove() {
   }
  };
 }

Here is the github link to the code for Queue built using array - Github - Queue using Resizing Array

Feel free to download or browse through the entire source for this project from github repository - Github - Basic Datastructures

Labels: , ,

Friday, December 20, 2013

Binary Tree Traversals

Binary tree is a special case of a tree in which there are no more than 2 children for any node. The children are called left and right nodes respectively based on the fact whether they are located on the left or right side of the parent node. Binary trees are extensively used in software engineering because it just takes O(log n) for doing most of the day to day operations – insert, update, delete and search. Traversal algorithms are very important concepts in binary trees because if you want to do any type of operation on a binary tree then as a first step, the tree needs to be traversed to find the nodes on which the desired operation need to be performed. The three widely used binary tree traversal algorithms are

1) Preorder traversal
Processing order of the nodes are – parent, all its left descendants and then the right descendants. In other words, Parent is processed before left sub-tree and right sub-tree are processed.

2) Inorder traversal
Processing order of the nodes are – all left descendants, parent and then the right descendants. In other words, left sub-tree is processed before parent and right sub-tree are processed.

3) Postorder traversal
Processing order of the nodes are – all left descendants, right descendants and then finally the parent descendants. In other words, all the children are processed before the parent is processed.

For the impatient code readers, the entire code base for this project can be accessed from my Github repository – Binary Tree Traversal algorithms.

Recursive Solution
A recursive solution best suits the situation where there is a bigger problem that can be broken down into smaller and similar sub problems and so the same solution can be applied over the sub-problems. It is imperative to have a base case after which the solution should start winding up. Recursion can be best understood when the whole process can be visualized with a stack.

Iterative Solution
An iterative solution best suits the situation where there is a bigger problem that can be broken down into smaller problems and every such smaller problem is iteratively solved one after another. There is no connection between an iteration and its successive iterations. As in the case of recursion, an iteration does not pause or wait until all the sub-iterations are complete. And that’s why we need an additional tool(aka data structure) so that we can adapt an iterative solution for tree-traversals. A stack is needed in an iterative solution so that it can be used to temporarily store the nodes in the needed order and then apply the solution or process the node that comes out of the stack.

Preorder traversal
Recursive solution is simple and self-explanatory.

public void preOrderTraversalRecursive(Node node) {
  if (node == null) {
   return;
  }
  
  System.out.println(node);
  if (node.getLeft() != null) {
   preOrderTraversalIterative(node.getLeft());
  }
  if (node.getRight() != null) {
   preOrderTraversalIterative(node.getRight());
  }
 }

Iterative solution for any traversal needs at least a stack. Preorder traversal is the simplest among all the traversal iterative algorithms. To start with, the root node is added to stack. From there on, we navigate deep into the left-most sub-tree. And while doing so, we keep processing the node that we are navigating through and we keep adding the right child of the node (if exists) to the stack. The left child is added too but it is popped out in the next iteration, and that’s how we navigate down the tree. While we pop out the nodes from the stack, we go over the same process – navigate, process and add the right child to stack if it exists.

public void preOrderTraversalIterative(Node node) {
Stack<Node> stack = new Stack<Node>();
  stack.push(node);
  
  while (!stack.isEmpty()) {
   Node poppedNode = stack.pop();
   System.out.println(poppedNode);
   if (poppedNode.getRight() != null) {
    stack.add(poppedNode.getRight());
   }
   
   if (poppedNode.getLeft() != null) {
    stack.add(poppedNode.getLeft());
   }
  }
}


Inorder traversal
The recursive solution is pretty simple. Given a node, keep navigating to the left-most node until a leaf node is reached. Once reached, process the leaf node, its parent and then the right sub-tree (again go through the same above process).

public void inOrderTraversalRecursive(Node node) {
  if (node == null) {
   return;
  }
  
  if (node.getLeft() != null) {
   inOrderTraversalRecursive(node.getLeft());
  }
  System.out.println(node);
  if (node.getRight() != null) {
   inOrderTraversalRecursive(node.getRight());
  }
 }

As expected the iterative solution uses a single stack. The in-order traversal algorithm processes the left sub-tree first from deep down node => which in turn means, navigate to the left-most leaf node. So, as a first step, navigate deep down into the left sub-tree. We keep pushing all the left-nodes to the stack when we navigate, so that when we pop out of the stack for the first time, it’s going to be the left-most leaf node. For every popped node, we check whether there is a right node, if there is, then we add that node and then followed by all left-nodes (if there are) for the right node (that we are working on) to the stack. Once that is done, we pop out a node from the stack and then repeat the same above process until the stack goes empty.

public void inOrderTraversalIterative(Node node) {
  if (node == null) {
   return;
  }

  Stack<Node> stack = new Stack<Node>();
  // Navigate to the left most node of the left sub-tree. During that process, push all the navigating nodes to the stack.
  while (node != null) {
   stack.push(node);
   node = node.getLeft();
  }
  
  while (!stack.isEmpty()) {
   Node currNode = stack.pop();
   System.out.println(currNode);
   
   /* If the current node has a right child, push it to stack and navigate to the left node of that right child if it exists. 
   Remember we need to process the right sub-tree of any parent node. So, add all left nodes of the right child to stack and 
   keep navigating to left till the leaf node */ 
   if (currNode.getRight() != null) {
    Node rightnode = currNode.getRight();
    stack.push(rightnode);
    if (rightnode.getLeft() != null) {
     Node rightsLeftnode = rightnode.getLeft();
     while (rightsLeftnode != null) {
      stack.push(rightsLeftnode);
      rightsLeftnode = rightsLeftnode.getLeft();
     }
    }
   }
  }
 }


Postorder traversal
As always the recursive solution is simple. Given a node, the left descendants are processed first followed by the right descendants and then the node in consideration is processed. It looks pretty simple to do using a recursive approach.

public void postOrderTraversalRecursive(Node node) {
  if (node == null) {
   return;
  }
  
  if (node.getLeft() != null) {
   postOrderTraversalRecursive(node.getLeft());
  }
  
  if (node.getRight() != null) {
   postOrderTraversalRecursive(node.getRight());
  }
  System.out.println(node);
 }

The iterative solution for postorder traversal is the most difficult of all. The below iterative solution uses a single stack. This algorithm may not look same as other solutions provided in internet. This solution worked well for the usecases that I tested and hopefully it works for everyone. The tough part of this solution is: Determining whether we are currently navigating down the tree or up the tree. If we don’t determine that, we might end up looping back and forth in an endless loop. How to identify whether we are going up or down? If we remember the previous node that was processed or added to the stack then based on that, we can tell the relationship of the current node to the previous node. It can be a child node or the parent node!! This determination would help us making a decision whether to move up or down.

On a broad view, there are 2 cases that need to be covered in this algorithm
1) If the current node is the parent of the previously processed node (the previously processed node could either be a left or right child) then it means we are going up the tree. That in turn means we have already processed the child sub-trees of the current node. So, it’s time to process the parent node and go for the next element in the stack.
2) The other situations could be:
a) The current node can be the left or right child of the previously processed node. In this case, we are going down the tree.
b) The current node is the root node.
c) The current node can be the right companion of the previously processed node.

For all the above usecases (a), (b) and (c), we call the special private method “navigateAndProcessNodesInPostOrder” method. navigateAndProcessNodesInPostOrder method takes care of pushing the current node, left child and right child (in that order) to stack if the nodes exist. After pushing the nodes, it navigates to the left child (if it exists) because precedence is given to the left node. If not it tries to navigate to the right child. If there are no child nodes then this method just processes it without the need of adding that to stack because it’s a leaf node. “NodeWrapper” object is used as a wrapper object to hold the previous processed node, the current node and the stack.

/**
  * An iterative solution for postorder traversal of a binary tree.
  * 
  * On a broad view, there are 2 cases that need to be covered in this algorithm
  * 1) If the current node is the parent of the previously processed node (the previously processed node could either be a 
  *   left or right child) then it means we are going up the tree. That in turn means we have already processed the child 
  *  sub-trees of the current node. So, it’s time to process the parent node and go for the next element in the stack.
  * 2) The other situations could be: 
  *  a) The current node can be the left or right child of the previously processed node. In this case, we are going down the tree. 
  *  b) The current node is the root node. 
  *  c) The current node can be the right companion of the previously processed node. 
  *  For all the above usecases, we call the special private method “navigateAndProcessNodesInPostOrder” method. 
  *  navigateAndProcessNodesInPostOrder  method takes care of pushing the current node, left child and right child (in that order) 
  *  to stack if the nodes exist. After pushing the nodes, it navigates to the left child (if it exists) because precedence is given 
  *  to the left node. If not it tries to navigate to the right child. If there are no child nodes then this method just processes 
  *  it without the need of adding that to stack because it’s a leaf node. “NodeWrapper” object is used as a wrapper object to hold 
  *  the previous processed node, the current node and the stack.
  * @param node Node Object
  * 
  */
 public void postOrderTraversalIterative(Node node) {
  if (node == null) {
   return;
  }
  
  Stack<Node> stack = new Stack<Node>();
  stack.push(node);
  Node prevNode = null;
  Node currNode = null;
  
  while (!stack.isEmpty()) {
   currNode = stack.pop();
   
   if (currNode.getLeft() == prevNode || currNode.getRight() == prevNode) {
    // If the current node is the parent of previously processed node. Navigating up the tree. So its enough just to process the node
    System.out.println(currNode);
    prevNode = currNode;
   } else {
    // If previously processed node was the parent of current node. i.e currently processing either the left or right child (navigating down).
    // If the node is the root node.
    // If the current node is the leaf node of a sub-tree. In this case previously processed node and current node are same.
    // If the current node being processed is the right companion of the previously processed node
    
    NodeWrapper nodeWrapper = new NodeWrapper(prevNode, currNode, stack);
    nodeWrapper = navigateAndProcessNodesInPostOrder(nodeWrapper);
    prevNode = nodeWrapper.getPrevNode();
    currNode = nodeWrapper.getCurrNode();
    stack = nodeWrapper.getStack();
   }
  }
 }
 
 /**
  * A helper method for post-order traversal - if given a node, it traverses and processes the sub-tree
  * NodeWrapper object is used to exchange prev, curr nodes and stack between the calling and called method
  * @param nodeWrapper
  * @return
  */
 private NodeWrapper navigateAndProcessNodesInPostOrder(NodeWrapper nodeWrapper) {
  Node currNode = nodeWrapper.getCurrNode();
  Node prevNode = nodeWrapper.getPrevNode();
  Stack<Node> stack = nodeWrapper.getStack();
  
  Node leftNode = currNode.getLeft();
  Node rightNode = currNode.getRight();
  if (leftNode != null  || rightNode != null) {
   // current node (if its a parent) is the last to be processed and so it has to be pushed to stack first
   stack.push(currNode);
   if (rightNode != null) {
    // If there is a right node, push it to stack
    stack.push(rightNode);
   }
   // If there is a left node, push it to stack
   if (leftNode != null) {
    stack.push(leftNode);
   }
   prevNode = currNode;
   
   // Left takes precedence. If there is a left node, go left else go right 
   if (leftNode != null) {
    currNode = currNode.getLeft();
   } else if (rightNode != null) {
    currNode = currNode.getRight();
   }
  } else { // its a leaf node, so process it
   System.out.println(currNode);
   prevNode = currNode;
  }
  nodeWrapper.setPrevNode(prevNode);
  nodeWrapper.setCurrNode(currNode);
  return nodeWrapper;
 }
 
  /**
  * An inner class NodeWrapper to encompass prevNode, currNode and stack for post-order traversal
  *
  */
 class NodeWrapper {
  private Node prevNode;
  private Node currNode;
  private Stack<Node> stack;
  
  NodeWrapper(Node prevNode, Node currNode, Stack<Node> stack) {
   this.prevNode = prevNode;
   this.currNode = currNode;
   this.stack = stack;
  }

  private Node getPrevNode() {
   return prevNode;
  }

  private Node getCurrNode() {
   return currNode;
  }

  private Stack<Node> getStack() {
   return stack;
  }

  private void setPrevNode(Node prevNode) {
   this.prevNode = prevNode;
  }

  private void setCurrNode(Node currNode) {
   this.currNode = currNode;
  }

  private void setStack(Stack<Node> stack) {
   this.stack = stack;
  }
  
 }


The entire code base for this project can be accessed from my Github repository – Binary Tree Traversal algorithms. I have added as many comments as possible in the code. Hope it will help everyone!!

Labels: , ,