Binary Tree Traversals (Inorder, Preorder and Postorder) in Javascript
In previous post we have learned about how can we create a binary search tree in javascript and tried some operations on binary tree like search a node in tree, finding height of tree. In this post we are explaining Inorder, Preorder and Postorder in Binary Tree.
You can check same here on my previous post
https://nodeblogger.com/binary-search-tree-in-javascript/
Lets see what is Inorder, Preorder and Postorder in Binary Search tree.
- Inorder (Left, Root, Right) : 4 2 5 1 3
- Preorder (Root, Left, Right) : 1 2 4 5 3
- Postorder (Left, Right, Root) : 4 5 2 3 1
Inorder Traversal
inorderTraversal(node = this.root){
if(node == null)
return;
this.inorderTraversal(node.left);
console.log(node.data);
this.inorderTraversal(node.right);
}
In case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order.
Preorder Traversal
//root->left->right
preorderTraversal(node = this.root){
if(node == null)
return;
console.log(node.data);
this.preorderTraversal(node.left);
this.preorderTraversal(node.right)
}
Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expression on of an expression tree
Postorder Traversal
//left->right->root
postorderTraversal(node = this.root){
if(node == null)
return;
this.postorderTraversal(node.left);
this.postorderTraversal(node.right);
console.log(node.data);
}
Postorder traversal is used to delete the tree.
Time Complexity: O(n)
References :
https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/