Tree Traversals, recursion is faster than iteration in python?

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?


Asked by: Alfred879 | Posted: 06-12-2021






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

Answered by: Brad275 | Posted: 07-01-2022



Similar questions

arrays - Can parallel traversals be done in MATLAB just as in Python?

Using the zip function, Python allows for loops to traverse multiple sequences in parallel. for (x,y) in zip(List1, List2): Does MATLAB have an equivalent syntax? If not, what is the best way to iterate over two parallel arrays at the same time using MATLAB?


python - Recursion - how do you extract from specific traversals

Lets say you have a string: abcde And a set of strings: ab, cde, abcd, a, bcd, cd You want to find all possible concatenations from the set that form the string. You can use recursion to traverse through all possible concatenations from the set, but how would you return only those that satisfy the solution? The possible combinations: ab - cde - yes ab - cd - no abcd - no a ...


python - Writing traversals to a file in python3.x issue

I am trying to traverse a heap, and write the traversal to a file but I am failing miserably. I keep getting an issue with the maximum traversal depth that spams my terminal when all I want is for the node to be printed out in the file.


recursion - Traverse tree and return a node instance after n traversals in python

The end goal is to copy a node from one tree to another tree. I want to visit each node in a binary tree and return a node instance after a number of traverses. I cannot seem to figure out how to return a specific node. Every time the node returned matches the id of the root node since I pass the root node to the function. class node(): def __init__(self): self.parent = None self.left =...


python - Can a directed graph have two DFS traversals?

Here is my DFS traversal algorithm (Recursive approach): def dfs(v,visited) : for i in Graph[v] : if i not in visited : visited.append(i) print(i) dfs(i,visited) n = int(input()) Graph = {} for i in range(n) : name= input(print("Enter ",i+1," vertex name")) list...


python - Traversals of Binary Trees

I am trying to implement in-order, pre-order, and post-order traversals of a binary tree. My implementation seems to work for trees with a small number of nodes (as I have checked by hand) but the online software I am using says there are cases that my implementation fails (it does not provide the input that causes my implementation to fail). I have looked through several other threads on this site but cannot seem to find ...






Still can't find your answer? Check out these communities...



PySlackers | Full Stack Python | NHS Python | Pythonist Cafe | Hacker Earth | Discord Python



top