Inorder Traversal of Tree in Python Returning a List

Question

I learnt implementing inorder traversal of a binary search tree:

def inorder(root): # root has val, left and right fields
    if root==None:
        return

    inorder(root.left)
    print(root.val)
    inorder(root.right)

Now, the problem is I do not want console output. I want to get the values in a list. I can't find a way to make the function return a list.

I tried s = [inorder(root)] but it doesn't work.

So, my question is:

1. Any way this could be done inside the inorder function, i.e. it should return a list rather than just print values.

2. Is there some generic way to make recusive functions return data structures instead of just outputting a print to console?

Answer 1

You can build up the list recursivly. Simply add the returned list from the left and right trees together with the value in the current node.

def inorder(root):
    if root==None:
        return []

    left_list = inorder(root.left)
    right_list = inorder(root.right)
    return left_list + [val] + right_list 

Answer 2

You can pass a list, and then append the values to it, like this-

def inorder(root,ans): # root has val, left and right fields
    if root==None:
        return

    inorder(root.left)
    ans.append(root.val)
    inorder(root.right)
ans=[]
inorder(root,ans)
print(ans)

Answering your second query:

Passing the data structure itself is the simplest solution. If you really want the function to "return" the output, One way is using list concatenation as @Shaido suggested, but it is slightly heavier on memory by unnecessarily creating a new singleton list at every recursive call.

A better solution would be using some static list(i. e. a fixed list that would be declared only once). But it's not available directly in python, because python suggests doing it by declaring it inside a class. (A good discussion here)