Binary tree traversal - inorder, preorder and postorder
Tree node definition
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
To build the tree nodes:
root = Node(0)
n1 = Node(1)
n2 = Node(2)
root.left = n1
root.right = n2
n3 = Node(3)
n4 = Node(4)
n1.left = n3
n1.right = n4
n5 = Node(5)
n6 = Node(6)
n2.left = n5
n2.right = n6
n7 = Node(7)
n8 = Node(8)
n3.left = n7
n3.right = n8
The tree looks like below:
0
/ \
1 2
/ \ / \
3 4 5 6
/ \
7 8
Pre-order traversal
def pre_order_traverse(node):
if node == None:
return
print(f"{node.val} ", end="")
pre_order_traverse(node.left)
pre_order_traverse(node.right)
pre_order_traverse(root)
print()
Output: 0 1 3 7 8 4 2 5 6
In-order traversal
def in_order_traverse(node):
if node == None:
return
in_order_traverse(node.left)
print(f"{node.val} ", end="")
in_order_traverse(node.right)
in_order_traverse(root)
print()
Output: 7 3 8 1 4 0 5 2 6
Post-order traversal
def post_order_traverse(node):
if node == None:
return
post_order_traverse(node.left)
post_order_traverse(node.right)
print(f"{node.val} ", end="")
post_order_traverse(root)
print()
Output: 7 8 3 4 1 5 6 2 0
Get tree size
def size(node):
if node == None:
return 0
return size(node.left) + 1 + size(node.right)
print(f"size: {size(root)}")
Output:
size: 9
Get tree depth
def depth(node):
if node == None:
return 0
return max(depth(node.left), depth(node.right)) + 1
print(f"depth: {depth(root)}")
Output:
depth: 4
Print all the paths in the tree
def printPaths(node, path):
if node == None:
return
# add node to the path
path.append(node.val)
if node.left == None and node.right == None:
# this is leaf node
print("path : ", end="")
for n in path:
print(f"{n} ", end="")
print()
else:
# search left subtree
printPaths(node.left, path)
# search right subtree
printPaths(node.right, path)
# remove node from path
path.pop()
printPaths(root, list())
Output:
path : 0 1 3 7
path : 0 1 3 8
path : 0 1 4
path : 0 2 5
path : 0 2 6
Check if path exists for target sum
def hasPathSum(node, sum):
if node == None:
return sum == 0
sum -= node.val
return hasPathSum(node.left, sum) or hasPathSum(node.right, sum)
print(hasPathSum(root, 7))
print(hasPathSum(root, 12))
print(hasPathSum(root, 10))
Output:
True
True
False