Trees

Tree traversal algorithms and binary tree operations.

Binary Tree Inorder Traversal

Left-Root-Right traversal of a binary tree.

How it works

Inorder traversal visits nodes in Left-Root-Right order. For binary search trees, inorder gives elements in sorted order. It can be implemented recursively or iteratively with a stack. Inorder is useful for validating BSTs and extracting sorted data.

Time Complexity

O(n)

Space Complexity

O(h)

def inorder(node, result):
  if not node: return
  inorder(node.left, result)
  result.append(node.val)
  inorder(node.right, result)
  return result

Binary Tree Level Order Traversal

BFS-based level-by-level traversal of a binary tree.

How it works

Level order (or breadth-first) traversal visits all nodes at each level before moving to the next. It uses a queue and is useful for finding the height, width, and other level-based properties of trees. It's also the foundation for many tree algorithms.

Time Complexity

O(n)

Space Complexity

O(w)

from collections import deque
def levelOrder(root):
  if not root: return []
  result, queue = [], deque([root])
  while queue:
    level = []
    for _ in range(len(queue)):
      node = queue.popleft()
      level.append(node.val)
      if node.left: queue.append(node.left)
      if node.right: queue.append(node.right)
    result.append(level)
  return result