bst traversals

bst_traversals.py

from collections import deque

class TreeNode[T]:
    val: 'T'
    left: 'TreeNode | None'
    right: 'TreeNode | None'
    def __init__(self, val: T, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# or preorder
def dfs(tree: TreeNode[str] | None):
    if not tree:
        return
    print(tree.val, end=' ')
    dfs(tree.left)
    dfs(tree.right)

# per level
def bfs[T](tree: TreeNode[T] | None):
    queue = deque([tree])

    while queue:
        # for each level
        for _ in range(len(queue)):
            node = queue.popleft()
            if node:
                print(node.val, end=' ')
                queue.append(node.left)
                queue.append(node.right)

def inorder[T](tree: TreeNode[T] | None):
    if not tree:
        return
    inorder(tree.left)
    print(tree.val, end=' ')
    inorder(tree.right)

def postorder[T](tree: TreeNode[T] | None):
    if not tree:
        return
    postorder(tree.left)
    postorder(tree.right)
    print(tree.val, end=' ')

# bfs F K D A H B E C G
# preorder = dfs F K A E C D H B G
# inorder E A C K F H D B G
# postorder E C A K H G B D F
example = TreeNode(
        'F',
        TreeNode(
            'K',
            TreeNode(
                'A',
                TreeNode('E'),
                TreeNode('C')
            ),
            None,
        ),
        TreeNode(
            'D',
            TreeNode('H'),
            TreeNode(
                'B',
                None,
                TreeNode('G')
            )
        )
)

dfs(example)
print()
bfs(example)
print()
inorder(example)
print()
postorder(example)
print()

leetcode = TreeNode(
        3,
        TreeNode(9),
        TreeNode(
            20,
            TreeNode(15),
            TreeNode(7)
        )
)

print()
dfs(leetcode)
print()
bfs(leetcode)
print()
inorder(leetcode)
print()
postorder(leetcode)
print()