Binary Tree Traversal
Data Structures and Algorithms Note
Breadth-First /Level Order Traversal: 1 2 3 4 5
Depth First Traversals:
> Preorder (Root, Left, Right) : 1 2 4 5 3
> Inorder (Left, Root, Right) : 4 2 5 1 3
> Postorder (Left, Right, Root) : 4 5 2 3 1
Unlike linear data structures can be traversed in only one way, trees can be traversed in various ways, especially these two ways:
1. Breadth First Traversal (BFT)/ Level Order Traversal
go to the specific level by keep go node.left/node.right until the level is 1(as if the root is one)
# Function to print level order traversal of tree
def printLevelOrder(root):
h = height(root)
for i in range(1, h+1):
printCurrentLevel(root, i)
# Print nodes at a current level
def printCurrentLevel(root, level):
if root is None:
return
if level == 1:
print(root.data, end=" ")
elif level > 1:
printCurrentLevel(root.left, level-1)
printCurrentLevel(root.right, level-1)In order to get the maximum width of the tree, use queue:
— — —-----
-> 4 3 2 1 ->
—------— —
def get_max_width(root):
# base case
if root is None:
return 0
q = []
max_width = 0
q.insert(0, root)
while q:
# Get the size of queue
# when the level order traversal for one level finishes
count = len(q)
# Update the maximum node count value
max_width= max(count, max_width)
# go through all the nodes in the current level
while (count != 0):
curr_node = q.pop()
count = count-1
if curr_node.left is not None:
q.insert(0, curr_node.left)
if curr_node.right is not None:
q.insert(0, curr_node.right) return max_width
2. Depth First Traversal (DFT)
- Preorder Traversal (Root L R)
def printPreorder(root):
if root:
# First print the data of node
print(root.val)# Then recur on left child
printPreorder(root.left)# Finally recur on right child
printPreorder(root.right)
- Inorder Traversal (L Root R)
def printInorder(root):
if root:
# First recur on left child
printInorder(root.left) # Then print the data of node
print(root.val) # Finally recur on right child
printInorder(root.right)
using stack
def printInorder(root):
# Set current to root of binary tree
current = root
# initialize stack
stack = []
while True:
# Reach the left most Node of the current Node
if current is not None:
stack.append(current)
current = current.left
# If there is nodes in the stack,
# pop the top node and print the data,
# then visit its right node
elif(stack):
current = stack.pop()
print(current.data)
current = current.right # break when there is no any node in the stack
else:
break
- Postorder Traversal (L Root R)
def printPostorder(root):
if root:
# First recur on left child
printPostorder(root.left)
# Then recur on right child
printPostorder(root.right)
# Finally print the data of node
print(root.val)How to choose
BFS starts visiting nodes from the root while DFS starts visiting nodes from leaves. So if the problem is to search the node that is closer to the root, then use BFS. And if the target node is close to a leaf, we would prefer DFS.
REFERENCE
https://www.geeksforgeeks.org/level-order-tree-traversal/
https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
https://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/
https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
https://www.geeksforgeeks.org/maximum-width-of-a-binary-tree/
