Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a Binary Tree, we can visit the nodes in a particular order – which is called Tree Traversal.
Binary Tree Pre-Order Traversal Algorithm
We visit the Node first then Recursively traverse the Left Tree and then Right Tree i.e. NLR.
1 2 3 4 5 6 | def preOrder(root): if root is None: return print(root.val) # visit Node preOrder(root.left) preOrder(root.right) |
def preOrder(root): if root is None: return print(root.val) # visit Node preOrder(root.left) preOrder(root.right)
The NLR of above tree is: 1,2,4,5,3,6
Binary Tree In-Order Traversal Algorithm
We recursively traverse the left tree, and then visit the node, and then traverse recursively the right tre i.e. LNR.
1 2 3 4 5 6 | def inOrder(root): if root is None: return inOrder(root.left) print(root.val) # visit Node inOrder(root.right) |
def inOrder(root): if root is None: return inOrder(root.left) print(root.val) # visit Node inOrder(root.right)
If we perform an inorder traversal to a Binary Search Tree, we will get a sorted list (in non-descending order).
For example:
1 / \ 0 2 / \ 1.5 3
Inorder traversal gives 0, 1, 1.5, 2, 3 which is in order.
Binary Tree Reverse In-Order Traversal Algorithm
The reverse in-order visits the nodes in RNL that is recursively traversing right tree, then visit node, then recursively traversing the left tree.
1 2 3 4 5 6 | def ReverseInOrder(root): if root is None: return ReverseInOrder(root.right) print(root.val) # visit Node ReverseInOrder(root.left) |
def ReverseInOrder(root): if root is None: return ReverseInOrder(root.right) print(root.val) # visit Node ReverseInOrder(root.left)
A Reverse In-order will print a sorted list in non-ascending order i.e. 3, 2, 1.5, 1, 0 (in above example).
Post Order Traversal Algorithm for Binary Tree
The post-order traversal visits the nodes in LRN order, which is recursively visiting left tree, then right tree, and visit the node last.
1 2 3 4 5 6 | def postOrder(root): if root is None: return postOrder(root.left) postOrder(root.right) print(root.val) # visit Node |
def postOrder(root): if root is None: return postOrder(root.left) postOrder(root.right) print(root.val) # visit Node
For above binary tree, the post-order traversal gives the order of: [0, 1.5, 3, 2, 1]
Breadth First Search Traversal
The Breadth First Search Traversal (BFS) is also one of the most important tree traversal algorithm. It traverses the binary tree in level-by-level order. For example, the above BFS traversal will give [0, 0, 2, 1.5, 3]. The implementation of a BFS is usually based on queue:
1 2 3 4 5 6 7 8 9 10 11 | def bfs(root): if root is None: return q = [root] while len(q) > 0: p = q.pop(0) print(p.val) # visit node if p.left: q.append(p.left) if p.right: q.append(p.right) |
def bfs(root): if root is None: return q = [root] while len(q) > 0: p = q.pop(0) print(p.val) # visit node if p.left: q.append(p.left) if p.right: q.append(p.right)
All Binary Tree Traversal Algorithms run at O(N) time and O(N) space (due to recursion/stack or queue).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Word Formation Algorithm using Hash Map
Next Post: Interval Intersection Algorithm