Tree Traversals, recursion is faster than iteration in python?

Question

I have implement tree preorder traversal in python, but found that my recursive version is faster than iteration version.

code is as below:

from __future__ import print_function
import time

class Tree():
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def build_tree(string):
    nodes = [0] + [Tree(s) for s in string]
    for i in range(2, len(nodes)):
        p = i/2
        if i%2 == 0:
            nodes[p].left = nodes[i]
        else:
            nodes[p].right = nodes[i]
    return nodes[1]

def preorder(tree):
    if tree:
        #  print(tree.value,end='')
        preorder(tree.left)
        preorder(tree.right)

def preorder2(tree):
    t = tree
    s = []
    while t or s:
        while t:
            #  print(t.value,end='')
            s.append(t)
            t = t.left
        if s:
            t = s.pop()
            t = t.right

def main():
    tree = build_tree('abcdefghi'*1000)
    t = time.time()
    for _ in range(100):
        preorder(tree)
    print(time.time() - t)
    t = time.time()
    for _ in range(100):
        preorder2(tree)
    print(time.time() - t)


if __name__ == '__main__':
    main()

results:

0.751042842865
1.0220580101

It means recursive version is about 25% faster. I search a lot, everybody says recursive should be slower, I just wonder why it is not the case in my code?

Answer 1

I believe you can simplify the iterator function and reduce the timing by eliminating one of the variables. Also, deque performs better than a set or a list in those kinds of cases.

from collections import deque

def preorder3(initial_node):
    queue = deque([initial_node])
    while queue:
        node = queue.pop()
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

The benchmarks:

from __future__ import print_function
from timeit import timeit

class Tree():
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def build_tree(string):
    nodes = [0] + [Tree(s) for s in string]
    for i in range(2, len(nodes)):
        p = i/2
        if i%2 == 0:
            nodes[p].left = nodes[i]
        else:
            nodes[p].right = nodes[i]
    return nodes[1]

def preorder(tree):
    if tree:
        preorder(tree.left)
        preorder(tree.right)

def preorder2(tree):
    t = tree
    s = []
    while t or s:
        while t:
            s.append(t)
            t = t.left
        if s:
            t = s.pop()
            t = t.right

from collections import deque

def preorder3(initial_node):
    queue = deque([initial_node])
    while queue:
        node = queue.pop()
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

tree = build_tree('abcdefghi'*100)

# Repetitions to time
number = 20

# Time it
print('preorder:  ', timeit('f(t)', 'from __main__ import preorder as f, tree as t', number=number))
print('preorder2: ', timeit('f(t)', 'from __main__ import preorder2 as f, tree as t', number=number))
print('preorder3: ', timeit('f(t)', 'from __main__ import preorder3 as f, tree as t', number=number))

Prints:

preorder:   0.0256490707397
preorder2:  0.0419111251831
preorder3:  0.0269520282745