Iterative tree walking

by

If you are doing a breadth first search the natural implementation is to push nodes into a queue, not to use recursion.

If you are doing a depth first search then recursion is the most natural way to code the traversal. However, unless your compiler optimizes tail recursion into iteration, your recursive implementation will be slower than an iterative algorithm, and will die with a stack overflow on a deep enough tree.

Some quick Python to illustrate the difference:

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)) )), (3, (5, (8)) ))
def bfs(t):
    to_visit = [t]
    while len(to_visit) > 0:
        c = to_visit[0]
        if type(c) is int:
            print c
        else: 
            print c[0]
            to_visit.append(c[1])
            if len(c) > 2: to_visit.append(c[2])
        to_visit = to_visit[1:]

def dfs(t):
    if type(t) is int:
        print t
        return 
    print t[0]
    dfs(t[1])
    if len(t) > 2: dfs(t[2]) 

bfs(t)
dfs(t)

More Related Contents:

  1. Non-recursive depth first search algorithm [closed]
  2. How to efficiently build a tree from a flat structure?
  3. What is the difference between tree depth and height?
  4. Iterating over a Binary Tree with O(1) Auxiliary Space
  5. In Order Successor in Binary Search Tree
  6. Hashing a Tree Structure
  7. reconstructing a tree from its preorder and postorder lists
  8. What are the differences between segment trees, interval trees, binary indexed trees and range trees?
  9. Why DFS and not BFS for finding cycle in graphs
  10. Print the biggest K elements in a given heap in O(K*log(K))?
  11. complexity in terms of big O
  12. Find all paths between two graph nodes
  13. Why is the constant always dropped from big O analysis?
  14. How can building a heap be O(n) time complexity?
  15. Which algorithm is faster O(N) or O(2N)?
  16. find the only unpaired element in the array
  17. Determine font color based on background color
  18. Nearest neighbors in high-dimensional data?
  19. Why do we use Base64?
  20. Heap vs Binary Search Tree (BST)
  21. Counting the adjacent swaps required to convert one permutation into another
  22. Algorithm for finding similar images
  23. design a stack such that getMinimum( ) should be O(1)
  24. Largest circle inside a non-convex polygon
  25. Generate a list of primes up to a certain number
  26. Best Fit Scheduling Algorithm
  27. O(n) algorithm to find the median of n² implicit numbers
  28. YouTube URL algorithm?
  29. Why is my recursive function so slow in R?
  30. What is the difference between Linear search and Binary search?

Leave a Comment