Traverse Binary Tree #
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def visit(self):
print(self.val)
BFS traversal #
Level-order traversal #
DFS traversal #
DFS traversal of a binary tree can be used to solve the following problems.
Maximum width, minimum depth and diameter of a binary tree
Binary tree iterator
Convert a binary tree into a mirror tree
Find k smallest/largest elements of a binary search tree
Boundary traversal of binary tree
Lowest common ancestor of two nodes in a binary tree
Construct a binary tree from pre-order and in-order traversal
Pre-order traversal #
Parent -> Left child -> Right child
Can be used to create a copy of the tree.
def preorder_recursive(node):
if node is None:
return
node.visit()
preorder_recursive(node.left)
preorder_recursive(node.right)
# Since parents are visited prior to children, we can push to and pop from stack
# in a loop as we go. The right child needs to pushed before left child so that
# left child is popped first.
def preorder_iterative(node):
if node is None:
return
stack = []
stack.append(node)
while stack:
node = stack.pop()
node.visit()
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
Reverse pre-order traversal #
Parent -> Right child -> Left child
def reverse_preorder_recursive(node):
if node is None:
return
node.visit()
reverse_preorder_recursive(node.right)
reverse_preorder_recursive(node.left)
# Since parents are visited prior to children, we can push to and pop from stack
# in a loop as we go. The left child needs to pushed before right child so that
# right child is popped first.
def reverse_preorder_iterative(node):
if node is None:
return
stack = []
stack.append(node)
while stack:
node = stack.pop()
node.visit()
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
In-order traversal #
Left child -> Parent -> Right child
Traversing a binary search tree (BST) in-order will visit the nodes in sorted order (ascending). Other applications include construction of BST, creating balanced BST from sorted array, determining if a tree is balanced, and finding k-smallest elements in a BST.
def inorder_recursive(node):
if node is None:
return
inorder_recursive(node.left)
node.visit()
inorder_recursive(node.right)
# Since left child has to be visited first, we need to push left children to the
# stack until we reach a leaf node. We then start popping the nodes and after
# visiting the popped nodes, push its right node, if it exist. If the right node
# contains a subtree (could be even a complete subtree), this subtree will be
# visited in-order as well.
def inorder_ietrative(node):
stack = []
while stack or node:
if node:
stack.append(node)
node = node.left
else:
node = stack.pop()
node.visit()
node = node.right
Reverse in-order traversal #
Right child -> Parent -> Left child
Traversing a binary search tree (BST) using reverse in-order method will visit the nodes in sorted order (descending). That means, it can be used to get K-largest elements in a BST as well.
def reverse_inorder_recusrive(node):
if node is None:
return
reverse_inorder_recusrive(node.right)
node.visit()
reverse_inorder_recusrive(node.left)
# Since right child has to be visited first, we need to push right children to \
# the stack until we reach a leaf node. We then start popping the nodes and
# after visiting the popped nodes, push its left node, if it exist. If the
# left node contains a subtree (could be even a complete subtree), this subtree
# will be visited in-order as well.
def reverse_inorder_iterative(node):
stack = []
while stack or node:
if node:
stack.append(node)
node = node.right
else:
node = stack.pop()
node.visit()
node = node.left
Post-order traversal #
Left child -> Right child -> Parent
Can be used to delete tree from leaf to root.
def postorder_recursive(node):
if node is None:
return
postorder_recursive(node.left)
postorder_recursive(node.right)
node.visit()
def postorder_iterative(node):
stack = []
last_seen = None
while stack or node:
if node:
stack.append(node)
node = node.left
else:
peek_node = stack[-1]
if peek_node.right and peek_node.right != last_seen:
node = peek_node.right
else:
peek_node.visit()
last_seen = stack.pop()
Reverse post-order traversal #
Right child -> Left child -> Parent
def reverse_postorder_recursive(node):
if node is None:
return
reverse_postorder_recursive(node.right)
reverse_postorder_recursive(node.left)
node.visit()
def reverse_postorder_iterative(node):
stack = []
last_seen_node = None
while stack or node:
if node:
stack.append(node)
node = node.right
else:
peek_node = stack[-1]
if peek_node.left and peek_node.left != last_seen_node:
node = peek_node.left
else:
peek_node.visit()
last_seen_node = stack.pop()
Test Code #
graph TB; A((1))-->B((2)) A-->C((3)); B-->E((4)) B-->F((5)) C-->H((6)) C-->I((7)) E-->M((null)) E-->J((8)) J-->K((9)) J-->L((10))
if __name__ == '__main__':
root = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3)
root.left = n2
root.right = n3
n4 = TreeNode(4)
n5 = TreeNode(5)
n2.left = n4
n2.right = n5
n6 = TreeNode(6)
n7 = TreeNode(7)
n3.left = n6
n3.right = n7
n8 = TreeNode(8)
n4.right = n8
n9 = TreeNode(9)
n10 = TreeNode(10)
n8.left = n9
n8.right = n10
print("In-order Recursive")
inorder_recursive(root)
print("In-order Iterarive")
inorder_ietrative(root)
print("Reverse In-order Recursive")
reverse_inorder_recusrive(root)
print("Reverse In-order Iterative")
reverse_inorder_iterative(root)
print("-------------------------")
print("Pre-order recursive")
preorder_recursive(root)
print("Pre-order Iterative")
preorder_iterative(root)
print("Reverse Pre-order recursive")
reverse_preorder_recursive(root)
print("Reverse Pre-order Iterative")
reverse_preorder_iterative(root)
print("-------------------------")
print("Post-order recursive")
postorder_recursive(root)
print("Post-order Iterative")
postorder_iterative(root)
print("Reverse Post-order recursive")
reverse_postorder_recursive(root)
print("Reverse Post-order Iterative")
reverse_postorder_iterative(root)
Resources #
A good resource to understand different tree traversal algorithms is Wikipedia. Also check EnjoyAlgorithms, StackOverflow and Testbook.