how to iterate through a binary search tree in python(no recursion)

Question

So far I have

def tree_iterate():
parent, current = None, self.root
lst = []
while current is not None: 
 if current.left not None:
  lst.append(current.item) 
  parent, current = current, current.left
 if current.right not None:
  lst.append(current.item)
  parent, current = current, current.right

(sorry about spacing I'm quite new at this)

I'm not quite sure how to iterate on both sides of the tree when current has left and right, without using recursion. My main goal is to have a list of all the nodes in this BSTenter code here

Why do you want to avoid recursion? It's the most concise and clear method of doing tree traversal. An easy iterative way to get all the nodes in your tree is to use breadth first search (BFS). You can use a queue (a simple python list) for this. — spinlok
– spinlok, Commented Mar 31, 2014 at 2:08

Gal Silberman · Accepted Answer · 2021-01-30 13:21:05Z

To get a list of all nodes in the BST iteratively, use Breadth-First Search (BFS). Note that this won't give you the nodes in sorted order:

queue = [root]
result = []
while queue:
    l = queue.pop(0)
    result.append(l)

    if l.left != None:
        queue.append(l.left)
    if l.right!= None:
        queue.append(l.right)

If you want the nodes in sorted order, you will need to simulate inorder traversal using a stack:

result = []
stack = [root]
while stack:
    stack[-1].visited = True
    if stack[-1].left != None and not stack[-1].left.visited:
        stack.append(stack[-1].left)
    else:
        node = stack.pop()
        result.append(node)
        if stack[-1].right != None:
            stack.append(stack[-1].right)

Collectives™ on Stack Overflow

how to iterate through a binary search tree in python(no recursion)

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related