🙏

জয়  শ্রী  রাম

🕉

---

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 

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)

Instructor: