Binary Trees

Binary Trees

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val   = val
        self.left  = left
        self.right = right

# Traversals
def inorder(node):   # left -> root -> right
    if not node: return []
    return inorder(node.left) + [node.val] + inorder(node.right)

def preorder(node):  # root -> left -> right
    if not node: return []
    return [node.val] + preorder(node.left) + preorder(node.right)

def postorder(node): # left -> right -> root
    if not node: return []
    return postorder(node.left) + postorder(node.right) + [node.val]

# Level-order BFS
from collections import deque
def level_order(root):
    if not root: return []
    result, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        result.append(level)
    return result

# Height O(n)
def height(node):
    if not node: return 0
    return 1 + max(height(node.left), height(node.right))