Preorder, Inorder, Postorder Traversal

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
You can skip this chapter, if you already know what Preorder, Inorder, Postorder Traversals are and how to implement them recursively. Rather read the chapter Iterative Traversal which would give you some really good insights about the powerful approach of the iterative traversal and how they are versatile in solving complex problems.
General Discussion
Preorder: The node we are on right now is visited first and then we visit left child (as well as the whole left subtree) followed by its right subtree (as well as the whole right subtree). I denote Preorder traversal by VLR : (V)isit the current node, then visit its (L)eft child, and then visit (R)ight child node.So, for the below tree, let's see what the Preorder traversal would look like this: 29 > 20 > 12 > 7 > 15 > 26 > 31 > 30
VLR 29 / \ VLR VLR 20 31 / \ / VLR VLR VLR 12 26 30 / \ VLR VLR 7 15
Inorder: The (L)eft childnode and left subtree of the current node is visited first, followed by the (V)isiting the current node and then visit the (R)ight childnode and right subtree. Let's denote Inorder traversal by LVR.
For the tree below,
the Inorder traversal would look like:
7 > 12 > 15 > 20 > 26 > 29 > 30 > 31.
LVR 29 / \ LVR LVR 20 31 / \ / LVR LVR LVR 12 26 30 / \ LVR LVR 7 15
One interesting property of Inorder traversal is that, for a BST it gives the items in sorted order (increasing order).
Postorder: Here the current node is visited at the end after visiting its left subtree followed by its right subtree. I'd denote Postorder traversal as LVR.
Postorder traversal of the below tree would look like:
7 > 15 > 12 > 26 > 20 > 30 > 31 > 29
LRV 29 / \ LRV LRV 20 31 / \ / LRV LRV LRV 12 26 30 / \ LRV LRV 7 15
In the above discussion, by "visit"
I mean visit the node and process it, i.e, do all the operations you need to do.
One example of operations needed to be done while visiting is adding the value of the node to an existing sum
if needed.
Recursive Implementation
Let's look at the recursive implementation of the Binary Tree DFS traversals before going into the iterative implementation discussion.
The Node class is defined as below:
Java code:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
Python 2 code:
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
Now the actual recursive implementations:
Preorder Traversal:
Java code:
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
preorderHelper(root, res);
return res;
}
private void preorderHelper(TreeNode currentNode, List<Integer> list) {
// first, visit and process current node
if(currentNode != null){
list.add(currentNode.val);
// next, visit and process left subtree
if (currentNode.left != null) {
preorderHelper(currentNode.left, list);
}
// and at the end, visit and process the right subtree
if (currentNode.right != null) {
preorderHelper(currentNode.right, list);
}
}
}
}
Python 2 code:
class Solution(object):
# :type root: TreeNode
# :rtype: List[int]
def preorderTraversal(self, root):
res = list()
self.preorderHelper(root, res)
return res
def preorderHelper(self, currentNode, res):
if currentNode != None:
#first, visit and process current node
res.append(currentNode.val)
#next, visit and process left subtree
if currentNode.left != None:
self.preorderHelper(currentNode.left, res)
#and at the end, visit and process the right subtree
if currentNode.right != None:
self.preorderHelper(currentNode.right, res)
Inorder Traversal:
Java code:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorderHelper(root, res);
return res;
}
private void inorderHelper(TreeNode currentNode, List<Integer> list) {
if(currentNode != null){
// first, visit and process left subtree
if (currentNode.left != null) {
inorderHelper(currentNode.left, list);
}
// now, visit and process current node
list.add(currentNode.val);
// and at the end, visit and process the right subtree
if (currentNode.right != null) {
inorderHelper(currentNode.right, list);
}
}
}
}
Python 2 code:
class Solution(object):
# :type root: TreeNode
# :rtype: List[int]
def inorderTraversal(self, root):
res = list()
self.inorderHelper(root, res)
return res
def inorderHelper(self, currentNode, res):
if currentNode != None:
#first, visit and process left subtree
if currentNode.left != None:
self.inorderHelper(currentNode.left, res)
#now, visit and process current node
res.append(currentNode.val)
#and at the end, visit and process the right subtree
if currentNode.right != None:
self.inorderHelper(currentNode.right, res)
Postorder Traversal:
Java code:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postorderHelper(root, res);
return res;
}
private void postorderHelper(TreeNode currentNode, List<Integer> list) {
if(currentNode != null){
// first, visit and process left subtree
if (currentNode.left != null) {
postorderHelper(currentNode.left, list);
}
// next, visit and process the right subtree
if (currentNode.right != null) {
postorderHelper(currentNode.right, list);
}
// and at the end, visit and process current node
list.add(currentNode.val);
}
}
}
Python 2 code:
class Solution(object):
# :type root: TreeNode
# :rtype: List[int]
def postorderTraversal(self, root):
res = list()
self.postorderHelper(root, res)
return res
def postorderHelper(self, currentNode, res):
if currentNode != None:
#first, visit and process left subtree
if currentNode.left != None:
self.postorderHelper(currentNode.left, res)
#next, visit and process the right subtree
if currentNode.right != None:
self.postorderHelper(currentNode.right, res)
#and at the end, visit and process current node
res.append(currentNode.val)
It is worth noting that these three types of traversals are nothing but Depth First Search.
Even though the recursive implementations are super simple for Preorder, Inorder and Postorder traversals, often times it becomes convoluted to think through for the beginners while trying to solve some complex Tree traversal problems using these recursive techniques. That is where iterative approach comes into play. Iterative implementations for these traversals are not as trivial as the recursive implementations but once you have a grasp on them they can be really powerful technique to solve complex tree traversal problems seamlessly. They would even make complex tree traversal problems look simple and easy to think through.
The next article is going to be very interesting, as we will be looking at the powerful iterative approach to these three types of traversals discussed above and how we can leverage the iterative
Even though the recursive implementations are super simple for Preorder, Inorder and Postorder traversals, often times it becomes convoluted to think through for the beginners while trying to solve some complex Tree traversal problems using these recursive techniques. That is where iterative approach comes into play. Iterative implementations for these traversals are not as trivial as the recursive implementations but once you have a grasp on them they can be really powerful technique to solve complex tree traversal problems seamlessly. They would even make complex tree traversal problems look simple and easy to think through.
The next article is going to be very interesting, as we will be looking at the powerful iterative approach to these three types of traversals discussed above and how we can leverage the iterative