Level Tree Traversal

Given a binary tree, visit all nodes in level order, starting from the root level.

This can be solved by queueing and dequeueing nodes of the tree in a loop. Each node is enqueued, dequeued, and printed once.

The loop runs once for each node, which makes time complexity O(n) for a tree with n nodes.

void levelTraversal(Node root) {
  if (root == null)
    return

  Queue q = new Queue()

  q.enqueue(root)

  while (Node n = q.dequeue()) {
    print(n.value)
  
    if (n.left)
      q.enqueue(n.left)

    if (n.right)
      q.enqueue(n.right)
  }
}