Inorder Binary Tree Traversal (using Python)

Question

I am trying to perform an inorder traversal of a tree. The code itself feels right, except it is not working properly. I have a feeling it has to either do with the if condition, how append works in python, or something perhaps with return. This works correctly if I use print instead of return, I think, but I want to be able to use return and still get the correct answer. For example, for the tree [1,None,2,3], my code returns [1] which is clearly incorrect.

Additionally is it possible to solve this problem using list comprehension? If so, any sample code would be greatly appreciated.

Here is my code:

    class Solution(object):
        def inorderTraversal(self, root):
            res = []
            if root:
                self.inorderTraversal(root.left)
                res.append(root.val)
                self.inorderTraversal(root.right)
            return res

Also before marking this as a duplicate, I know in order traversals have been asked on Stackoverflow (plenty of times), but none of them helped me understand why my understanding is wrong. I would be so grateful if someone helped me learn how to correct my approach versus simply posting another link without explanation. Thank you so much!

Solution 1

The reason this doesn't work is that res only has the value of the first node you give it appended to it; each time you recursively recall the function, it just makes a new res. It is a simple fix though, as follows:

class Solution(object):
    def inorderTraversal(self, root):
        res = []
        if root:
            res = self.inorderTraversal(root.left) 
            res.append(root.val)
            res = res + self.inorderTraversal(root.right)
        return res

In this, it returns the left branch, the value, and then the right. This can be done much more briefly as follows:

class Solution(object):
    def inorderTraversal(self, root):
        return (self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)) if root else []

Solution 2

Use this instead , a simple recursion ::

class Node:
    def __init__(self,key):
        self.left = None
        self.right = None
        self.val = key

def printInorder(root):
    if root:
        printInorder(root.left)
        print(root.val)
        printInorder(root.right)

def printPostorder(root):
    if root:
        printPostorder(root.left)
        printPostorder(root.right)
        print(root.val)

def printPreorder(root):
    if root:
        print(root.val)
        printPreorder(root.left)
        printPreorder(root.right)

# Driver code
root = Node(1)
root.left      = Node(2)
root.right     = Node(3)
root.left.left  = Node(4)
root.left.right  = Node(5)
print "Preorder traversal of binary tree is"
printPreorder(root)

print "\nInorder traversal of binary tree is"
printInorder(root)

print "\nPostorder traversal of binary tree is"
printPostorder(root)

Source :: here

Solution 3

@Benedict Randall Shaw's answer is already perfect. I just want to add some fun to it in a pythonic way. Although the doc does not suggest using a mutable object as default parameter, this will somewhat simplify the code by treating the default mutable list as a class member of the python function.

The difference is only the += is replaced by =, since the res is always the same list object inside the function before the function object is garbage collected.

def inorderTraversal(root, res=[]):
    if root:
        res = inorderTraversal(root.left)
        res.append(root.val)
        res = inorderTraversal(root.right)
return res

Comments

[Jane Sully]

Thank you so much! This makes perfect sense.

[Nicholas Johnson]

Doesn't each call to inorderTraversal reset your results list to an empty string since it's the first thing you do in the function?

[Benedict Randall Shaw]

@NicholasJohnson no; each call to inorderTraversal contains its own independent instance of res, which is unique to that call.

[MLKing]

The problem with this approach is that the list 'res' is maintained throughout the lifetime of the function 'inorderTraversal( )'. Multiple calls to the function will keep on appending to the 'res' list.