Skip to content

Instantly share code, notes, and snippets.

@dineshrajpurohit
Last active September 27, 2018 05:38
Show Gist options
  • Save dineshrajpurohit/9836947c0e3afc5806b7 to your computer and use it in GitHub Desktop.
Save dineshrajpurohit/9836947c0e3afc5806b7 to your computer and use it in GitHub Desktop.
Preorder, Postorder,Inorder and Levelorder traversal of rooted trees using Javascript
/**
*
* 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 |
* |___________|___________| |___________|____________| |___________|___________|
*
*
*
*/
TRVSL = {};
/**
*
* Dinesh
*
* ListNode
* ________________________
* | Parent Link |
* |________________________|
* | Item |
* |________________________|
* |1st Child |next sibling|
* |___________|____________|
*
*/
TRVSL.TreeNode = function(){
this.item = null;
this.parent = null;
this.firstChild = null;
this.nextSibling = null;
/**
* Preorder traversal
*
* Recursive method to visit itself before visiting the children
* e.g Directory structure
*/
this.preorder = function(){
this.visited();
if(this.firstChild != null){
this.firstChild.preorder();
}
if(this.nextSibling != null){
this.nextSibling.preorder();
}
}
/**
* Postorder traversal
*
* Recursive method to visit the children before visiting itself
* e.g To find the total size of the directory
*/
this.postorder = function(){
if(this.firstChild != null){
this.firstChild.postorder();
}
this.visited();
if(this.nextSibling != null){
this.nextSibling.postorder();
}
}
/**
* Inorder traversal
*
* First child nodes are vsited then the parent node and thens sibling chile node and their parents
*/
this.inorder = function(){
if(this.firstChild != null){
this.firstChild.inorder();
}
if(this.nextSibling != null){
this.nextSibling.inorder();
}
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
*/
this.levelorder = function(){
var queue = new Array();
queue.push(this);
while(queue.length > 0){
var node = queue.shift();
console.log("Visited Node: "+node.item);
if(node.firstChild != null){
queue.push(node.firstChild);
if(node.firstChild.nextSibling != null){
queue.push(node.firstChild.nextSibling);
}
}
}
}
this.visited = function(){
console.log("Current Node visited: "+this.item);
}
}
/**
* 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
*
*/
TRVSL.TreeList = function(){
this.root = null;
this.size = null;
this.createBasicTree = function(){
var home = createNode("Home",null,null,null);
this.root = home;
var users = createNode("Users",home,null,null);
home.firstChild = users;
var user1 = createNode("User1",users,null,null);
users.firstChild = user1;
var user2 = createNode("User2",users,null,null);
user1.nextSibling = user2;
var user3 = createNode("User3",users,null,null);
user2.nextSibling = user3;
var files = createNode("Files",home, null,null);
users.nextSibling = files;
var file1 = createNode("File1",files,null,null);
files.firstChild = file1;
var desktop = createNode("Desktop",user1,null,null);
user1.firstChild = desktop;
var file2 = createNode("File2",files,null,null);
file1.nextSibling = file2;
var languages = createNode("Languages",home,null,null);
files.nextSibling = languages;
var javaL = createNode("Java",languages,null,null);
languages.firstChild = javaL;
var jsL = createNode("JS",languages,null,null);
javaL.nextSibling = jsL;
}
var createNode = function(item,parent, firstChild, nextSibling){
var node = new TRVSL.TreeNode();
node.item = item;
node.parent = parent;
node.firstChild = firstChild;
node.nextSibling = nextSibling;
return node;
}
this.getRoot = function(){
return this.root;
}
}
var tree = new TRVSL.TreeList();
tree.createBasicTree();
console.log("Tree:");
var root = tree.getRoot();
console.log("Preorder Traversal");
root.preorder();
console.log("Postorder Traversal");
root.postorder();
console.log("Inorder Traversal");
root.inorder();
console.log("Level Order");
root.levelorder();
/**
* OUTPUT
* Preorder Traversal
* Current Node visited: Home
* Current Node visited: Users
* Current Node visited: User1
* Current Node visited: Desktop
* Current Node visited: User2
* Current Node visited: User3
* Current Node visited: Files
* Current Node visited: File1
* Current Node visited: File2
* Current Node visited: Languages
* Current Node visited: Java
* Current Node visited: JS
*
* Postorder Traversal
* Current Node visited: Desktop
* Current Node visited: User1
* Current Node visited: User2
* Current Node visited: User3
* Current Node visited: Users
* Current Node visited: File1
* Current Node visited: File2
* Current Node visited: Files
* Current Node visited: Java
* Current Node visited: JS
* Current Node visited: Languages
* Current Node visited: Home
*
* Inorder Traversal
* Current Node visited: Desktop
* Current Node visited: User3
* Current Node visited: User2
* Current Node visited: User1
* Current Node visited: File2
* Current Node visited: File1
* Current Node visited: JS
* Current Node visited: Java
* Current Node visited: Languages
* Current Node visited: Files
* Current Node visited: Users
* Current Node visited: Home
*
* Level Order
* Visited Node: Home
* Visited Node: Users
* Visited Node: Files
* Visited Node: User1
* Visited Node: User2
* Visited Node: File1
* Visited Node: File2
* Visited Node: Desktop
*
**/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment