Teaching Kids Programming – Converting Breadth First Search Algorithm to Iterative Preorder Order (Depth First Search) for a Binary Tree | ninjasquad
Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a Binary Tree:
The level-by-level order can be done via Breadth First Search Algorithm where we use a queue (e.g. double-ended queue). The order is 4-85-016 for the above binary tree.
The standard BFS code for performing a level-by-level order in a given binary tree (root):
1 2 3 4 5 6 7 8 9 10 11 |
def bfs(root): if root is None: return q = deque([root]) while q: cur = q.popleft() yield cur if cur.left: q.append(cur.left) if cur.right: q.append(cur.right) |
def bfs(root): if root is None: return q = deque([root]) while q: cur = q.popleft() yield cur if cur.left: q.append(cur.left) if cur.right: q.append(cur.right)
If we change the queue (dequeu) to stack, and replace the popleft() with pop() as we are taking from the top of the stack – this will become a Reverse Preorder Traversal algorithm – NRL (Node-Right-Left):
1 2 3 4 5 6 7 8 9 10 11 |
def reversePreorder(root): if root is None: return q = [root] while q: cur = q.pop() yield cur if cur.left: q.append(cur.left) if cur.right: q.append(cur.right) |
def reversePreorder(root): if root is None: return q = [root] while q: cur = q.pop() yield cur if cur.left: q.append(cur.left) if cur.right: q.append(cur.right)
As the stack push/pop gives the reverse order, we can swap around the pushing of left and right nodes, that is, push the right nodes and then left node, this will give the Preorder Traversal Algorithm.
1 2 3 4 5 6 7 8 9 10 11 |
def preorder(root): if root is None: return q = [root] while q: cur = q.pop() yield cur if cur.right: q.append(cur.right) if cur.left: q.append(cur.left) |
def preorder(root): if root is None: return q = [root] while q: cur = q.pop() yield cur if cur.right: q.append(cur.right) if cur.left: q.append(cur.left)
If implementeed using Recursion, the Recursive Preorder Traversal Algorithm:
1 2 3 4 5 6 |
def preorder(root): if root is None: return yield cur yield from preorder(root.left) yield from preorder(root.right) |
def preorder(root): if root is None: return yield cur yield from preorder(root.left) yield from preorder(root.right)
The time/space complexity for the above traversal algorithms are O(N) where N is the number of the nodes in the given binary tree.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading…
536 words
Last Post: Teaching Kids Programming – Passing Item From One End to Another (Who Has It After N Seconds: Math/Simulation)
Next Post: Teaching Kids Programming – Split With Minimum Sum (Sort the Digits, Greedy)
Source: Internet