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