Given a binary tree, implement a function to perform a Breadth-First Search (BFS) or Depth-First Search (DFS).

Code Playground
JavaScript (V8)
Loading...
Console Output
// Output will appear here...
// For React: ReactDOM.createRoot(rootElement).render(<App />);
Recommended Answer

Assume a tree node structure: class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }

Breadth-First Search (BFS):

Explores the tree level by level. Uses a queue.

function bfs(root) {
  if (!root) return [];
  
  const queue = [root];
  const result = [];
  
  while (queue.length > 0) {
    const currentNode = queue.shift(); // Dequeue
    result.push(currentNode.val);
    
    if (currentNode.left) queue.push(currentNode.left);
    if (currentNode.right) queue.push(currentNode.right);
  }
  return result;
}

Depth-First Search (DFS - Pre-order traversal, recursive):

Explores as far as possible along each branch.

function dfs(root) {
  const result = [];
  
  function traverse(node) {
    if (!node) return;
    
    result.push(node.val); // Process node (Pre-order)
    traverse(node.left);
    traverse(node.right);
  }
  
  traverse(root);
  return result;
}