Preorder, Postorder,Inorder and Levelorder traversal of rooted trees using Java

RootedTreeTraversals.java

/**
 * 
 *  Dinesh
 * 
 *  RootedTreeTraversal
 *   - Preorder Traversal
 *   - Postorder Traversal
 *   - Inorder Traversal
 *   - Levelorder Traversal
 * 
 *  We will have to create a special Linked list to store the values of the rooted tree as shown in the figure below
 *  
 *  Linked List fields:
 *  Head - pointing to the first node of the list (The root of the tree)
 *  Size - Total number of nodes in the tree
 *  
 *  Representation:
 *   - Every node will have reference to the parent Node except the Root node which does not have any parent.
 *   - Every node will point to its left child except the leaf nodes where the first child pointer will be null;
 *   - Every node (except the root node) will point to its  first sibling.
 * 
 *   Home
 *   	- Users
 *      - Files
 *      - Languages
 *				    _______________________
 *				   |		NULL   	   |
 *				   |_______________________|
 *				   |		Home 	   |
 *		------------------>|_______________________|
 *		|	|----------|-- (users) |  NULL	   |<-------------------|
 *		|	|	   |___________|___________|	 	        |
 *		|	|				^		        |
 *		|	|				|	         	|
 *   ___________|_______|____		________________|________	  ______|_________________
 *  |			|   |		| 		       	 |	 |	|                |
 *  |_______________________|		|________________________|	 |_______________________|
 *  |		Users 	    |		|	Files		 |	 |	Languages	 |
 *  |_______________________|		|________________________|	 |_______________________|
 *  | NULL	| (files)  -|---------->| NULL      |	(langs)	-|------>|	NULL	|  NULL	 |
 *  |___________|___________|		|___________|____________|	 |___________|___________|
 *
 *
 *
 */
 
 /**
  *  Very basic RootedTreeList class
  * 
  */
import java.util.Queue;

public class RootedTreeList {
	public RootedTreeNode root;
	private int size;
	
	public RootedTreeList(){
		this.root = null;
		this.size = 0;
	}
	
	/**
	 * Generate a Rooted tree - Manual
	 * 
	 * Rooted tree node is basically a directory structure 
	 * 
	 *  home
	 *  	users
	 *  		user1
	 *  			Desktop
	 *  		user2
	 *  		user3
	 *  	files
	 *  		file1
	 *  		file2
	 *  	languages
	 *  		Java
	 *  		JS 	
	 * 
	 */
	public void generateRootedTree(){		
		RootedTreeNode home = createBasicNode("Home", null, null, null);
		this.root = home;
		
		//Creating users Node
		RootedTreeNode users = createBasicNode("Users", home, null, null);
		home.firstChild = users;
		
		//creating user1 node
		RootedTreeNode user1 = createBasicNode("User1", users, null, null);
		users.firstChild = user1;
		
		// user1's child Desktop
		RootedTreeNode desktop = createBasicNode("Desktop", user1, null, null);
		user1.firstChild = desktop;
		
		//creating user2 node
		RootedTreeNode user2 = createBasicNode("User2", users, null, null);
		user1.nextSibling = user2;
		//user2.firstChild = null;
		
		//creating user3 node
		RootedTreeNode user3 = createBasicNode("User3", users, null, null);		
		user2.nextSibling = user3;
		//user3.nextSibling = null;
		//user3.firstChild = null;
		
		// Files Nodes
		RootedTreeNode files = createBasicNode("Files", home, null, null);
		users.nextSibling = files;
		
		// File1 Node
		RootedTreeNode file1 = createBasicNode("File1", files, null, null);
		files.firstChild = file1;
		
		//File2 Node
		RootedTreeNode file2 = createBasicNode("File2", files, null, null);
		file1.nextSibling = file2;
		
		//Languages Nodes
		RootedTreeNode langs = createBasicNode("Languages", home, null, null);
		files.nextSibling = langs;
		
		// Java Node
		RootedTreeNode javaL = createBasicNode("Java", langs, null, null);
		langs.firstChild = javaL;
		
		// JS
		RootedTreeNode js = createBasicNode("JS", langs, null, null);
		javaL.nextSibling = js;
		
	}
	
	/**
	 * 
	 * @param item - Item of the Node
	 * @param parent - Parent of the node
	 * @param nextSibling - Next sibling of the Node
	 * @param firstChild - First (leftmost) child of the node
	 * @return - the newly created node
	 * 
	 *  Basic Helper function which creates a node and assign the default values to the pointers
	 *  
	 */
	public RootedTreeNode createBasicNode(Object item, RootedTreeNode parent, RootedTreeNode nextSibling, RootedTreeNode firstChild){
		 RootedTreeNode node= new RootedTreeNode();
		 node.item = item;
		 node.parent = parent;
		 node.nextSibling = nextSibling;
		 node.firstChild = firstChild;
		 size +=1;
		 return node;
	}
	
	/**
	 * 
	 * @return - Root Node
	 * 
	 *  Retrieve the Root node of the Tree
	 * 
	 */
	public RootedTreeNode getRoot(){
		return this.root;
	}
	
	public static void main(String[] args){
		RootedTreeList list = new RootedTreeList();
		list.generateRootedTree();
		RootedTreeNode root = list.getRoot();
		
		System.out.println();
		System.out.println("Preorder Traversal:");
		root.preorder();
		
		System.out.println();
		System.out.println("Postorder Traversal:");
		root.postorder();
			
		System.out.println();
		System.out.println("Inorder Traversal:");
		root.inorder();
		
		System.out.println();
		System.out.println("Levelorder Traversal:");
		root.levelorder();
		
	}
}

/**
 * 
 *  Dinesh
 *
 *   ListNode
 *   ________________________
 *  |	   Parent Link       |
 *  |________________________|
 *  |		Item 	     |
 *  |________________________|
 *  |1st Child  |next sibling|
 *  |___________|____________|	
 *  
 */
class RootedTreeNode{
	Object item;
	RootedTreeNode parent;
	RootedTreeNode nextSibling;
	RootedTreeNode firstChild;
	
	/**
	 * Preorder traversal
	 * 
	 *  Recursive method to visit itself before visiting the children 
	 *  e.g Directory structure
	 */
	public void preorder(){
		this.visited();
		if(firstChild != null){
			firstChild.preorder();
		}
		if(nextSibling != null){
			nextSibling.preorder();
		}
	}
	
	/**
	 * Postorder traversal
	 * 
	 *  Recursive method to visit the children before visiting itself 
	 *  e.g To find the total size of the directory
	 */
	public void postorder(){
		if(firstChild != null){
			firstChild.postorder();
		}
		this.visited();
		if(nextSibling != null){
			nextSibling.postorder();
		}
	}
	
	/**
	 * Inorder traversal
	 * 
	 * First child nodes are vsited then the parent node and thens sibling chile node and their parents
	 */
	public void inorder(){
		if(firstChild != null){
			firstChild.postorder();
		}
		if(nextSibling != null){
			nextSibling.postorder();
		}
		this.visited();
	}
	
	/**
	 * Levelorder traversal is done only in binary trees 
	 * In levelorder every node on the same level are visited at a time.
	 *  
	 *   			    Home
	 *   			  /	  \
	 *   			Users	   Files
	 *   		     /     \       /     \
	 *   		user1	user2  File1   File2
	 *		 /
	 *            Desktop
	 *       
	 *       Level Order: Home --> Users --> Files --> user1 --> user2 --> File1 --> File2 --> Desktop
	 */
	public void levelorder(){
		Queue<RootedTreeNode> q = new java.util.LinkedList<RootedTreeNode>();
		q.add(this);
		while(!q.isEmpty()){
			RootedTreeNode node = q.remove();
			System.out.println("Visited Node: "+node.item);
			if(node.firstChild != null){
				q.add(node.firstChild);
				if(node.firstChild.nextSibling != null){
					q.add(node.firstChild.nextSibling);
				}
			}
		}
	}
	
	/**
	 * Helper function to displays the node which is currently visited
	 * 
	 * Can be modified to do some more task
	 * 
	 */
	public void visited(){
		System.out.println("Visited Node: "+this.item);
	}
}


/**
 * 
 * OUTPUT
 * 
 * Preorder Traversal:
 * Visited Node: Home
 * Visited Node: Users
 * Visited Node: User1
 * Visited Node: Desktop
 * Visited Node: User2
 * Visited Node: User3
 * Visited Node: Files
 * Visited Node: File1
 * Visited Node: File2
 * Visited Node: Languages
 * Visited Node: Java
 * Visited Node: JS
 *
 * Postorder Traversal:
 * Visited Node: Desktop
 * Visited Node: User1
 * Visited Node: User2
 * Visited Node: User3
 * Visited Node: Users
 * Visited Node: File1
 * Visited Node: File2
 * Visited Node: Files
 * Visited Node: Java
 * Visited Node: JS
 * Visited Node: Languages
 * Visited Node: Home
 * 
 * Inorder Traversal:
 * Visited Node: Desktop
 * Visited Node: User1
 * Visited Node: User2
 * Visited Node: User3
 * Visited Node: Users
 * Visited Node: File1
 * Visited Node: File2
 * Visited Node: Files
 * Visited Node: Java
 * Visited Node: JS
 * Visited Node: Languages
 * Visited Node: Home
 * 
 * Levelorder Traversal:
 * Visited Node: Home
 * Visited Node: Users
 * Visited Node: Files
 * Visited Node: User1
 * Visited Node: User2
 * Visited Node: File1
 * Visited Node: File2
 * Visited Node: Desktop
 * 
 *
 */