Inorder Binary Tree Traversal (using Python)

@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

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

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 []