CODEWITHSUNDEEP
pythonrecursion
Andre
Andre

Reputation: 1661

Understanding Recursion on Tree Traversals

I am trying to understand how recursion works and how traversing a Binary Tree works.

Okay so from what I know, recursion is calling a function within it self. Kind of like looping.

Now I was given the code on how to do a postOrder traversal on a Binary Tree.

(Note this is not my code, I am just trying to understand how recursion works through this code)

 # Definition for a  binary tree node
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None

 class Solution:
     # @param root, a tree node
     # @return a list of integers

 def postorderTraversal(self, root):
    solution = []
    self.postorderTraversalRec(root, solution)
    return solution

 def postorderTraversalRec(self, root, solution):
    if root == None:
        return
    self.postorderTraversalRec(root.left, solution)
    self.postorderTraversalRec(root.right, solution)
    solution.append(root.val)

Now from what I understand a PostOrder traversal goes right-left-middle so child first then parent.

Here are the 2 lines where I think recursion is taking place.

    self.postorderTraversalRec(root.left, solution)
    self.postorderTraversalRec(root.right, solution)

From what I can understand is that the first line tells the program to recursively go through all the left nodes till it reaches the end. Then it tell the program to go through all the left hand nodes till it reaches the end.

But the problem I am facing is that, I cannot understand how this does a PostOrder traversal. To me it looks like a PreOrder traversal.

Upvotes: 0

Views: 1054

Answers (1)

dano
dano

Reputation: 94871

Post-order traversal is as follows:

  1. Traverse the left subtree.
  2. Traverse the right subtree.
  3. Visit the root.

Which is exactly what is happening here. For any given node (root), first you visit the left sub-tree (root.left), then the right sub-tree (root.right), then node itself (root.val).

The "pre" or "post" part of the traversal-type refers to when the value of the current node is visited, either before visiting the child nodes (pre-), after (post-), or even between visiting each child node (in-order traversal). In your example code the current node's value is visited after traversing the children. So, it's post-order traversal.

Upvotes: 2

Related Questions