SimuVedaAlgorithms Lab Open in the lab

Trees / Beginner

Level-Order Traversal Visualizer

Visit the tree one level at a time from top to bottom, using a queue.

Start the Level-Order Traversal simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(w)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Put the root 50 in the queue.
  2. Take 50 from the front of the queue.
  3. Visit 50.
  4. Add its left child 30 to the queue.
  5. Add its right child 70 to the queue.
  6. Take 30 from the front of the queue.
  7. Visit 30.
  8. Add its left child 20 to the queue.
  9. Add its right child 40 to the queue.
  10. Take 70 from the front of the queue.
  11. Visit 70.
  12. Add its left child 60 to the queue.
  13. Add its right child 80 to the queue.
  14. Take 20 from the front of the queue.
  15. Visit 20.
  16. Take 40 from the front of the queue.
  17. Visit 40.
  18. Add its left child 35 to the queue.
  19. Take 60 from the front of the queue.
  20. Visit 60.
  21. … 4 more steps …
  22. Visit 35.
  23. Take 65 from the front of the queue.
  24. Visit 65.
  25. Done. Visit order: 50, 30, 70, 20, 40, 60, 80, 35, 65.

Try it with your own input →

Level-order traversal in Java, Python, C++, C and JavaScript

void levelOrder(Node root) {
  Queue<Node> q = new LinkedList<>();
  q.add(root);
  while (!q.isEmpty()) {
    Node n = q.poll();
    visit(n);
    if (n.left != null) q.add(n.left);
    if (n.right != null) q.add(n.right);
  }
}
from collections import deque

def level_order(root):
    q = deque()
    q.append(root)
    while q:
        n = q.popleft()
        visit(n)
        if n.left:
            q.append(n.left)
        if n.right:
            q.append(n.right)
void levelOrder(Node* root) {
  queue<Node*> q;
  q.push(root);
  while (!q.empty()) {
    Node* n = q.front(); q.pop();
    visit(n);
    if (n->left) q.push(n->left);
    if (n->right) q.push(n->right);
  }
}
#define MAXN 1000

void levelOrder(struct Node* root) {
  struct Node* q[MAXN]; int head = 0, tail = 0;
  q[tail++] = root;
  while (head < tail) {
    struct Node* n = q[head++];
    visit(n);
    if (n->left) q[tail++] = n->left;
    if (n->right) q[tail++] = n->right;
  }
}
function levelOrder(root) {
  const q = [];
  q.push(root);
  let head = 0;
  while (head < q.length) {
    const n = q[head++];
    visit(n);
    if (n.left !== null) q.push(n.left);
    if (n.right !== null) q.push(n.right);
  }
}

In an interview

This is BFS on a tree. It solves "right side view", "zigzag order" and "minimum depth".

More trees