Traverse DOM tree

You are required to implement a function that traverses the DOM tree and returns an array of all the elements in the tree.

Constraints

• The input root is guaranteed to be a valid DOM element.
• The tree can have any number of nested elements.

Example Input

<div id="root">
    <div id="child1">
        <span id="child1_1"></span>
    </div>
    <div id="child2">
        <span id="child2_1"></span>
        <span id="child2_2"></span>
    </div>
</div>

<script>
    const rootElement = document.getElementById('root');
    console.log(getAllElements(rootElement));
</script>

Output

[
    <div id="root">...</div>,
    <div id="child1">...</div>,
    <span id="child1_1"></span>,
    <div id="child2">...</div>,
    <span id="child2_1"></span>,
    <span id="child2_2"></span>
]

Solution 1: DFS

To solve this problem, we can use a recursive depth-first traversal approach. The function getAllElements will start from the given root element and traverse each child node, collecting them in an array.

function getAllElements(root) {
    const result = [];

    function dfs(node) {
        result.push(node);
        for (let i = 0; i < node.childNodes.length; i++) {
            const child = node.childNodes[i];
            if (child.nodeType === 1) { // Only consider element nodes
                dfs(child);
            }
        }
    }

    // Start traversal from the root element
    dfs(root);

    return result;
}

// Example usage:
// Assuming the DOM structure from Example 1
document.addEventListener('DOMContentLoaded', () => {
  const rootElement = document.getElementById('root');
  console.log(getAllElements(rootElement));
});

Complexity

• Time complexity: O(N)
• Space complexity: O(N)

Solution 2: BFS

function getAllElements(root) {
  const result = [];
  if (!root) return result;
  
  const queue = [root];
  
  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    for (const child of node.children) {
      queue.push(child);
    }
  }
  
  return result;
}

// Example usage:
// Assuming the DOM structure from Example 1
document.addEventListener('DOMContentLoaded', () => {
  const rootElement = document.getElementById('root');
  console.log(getAllElements(rootElement));
});

Complexity

• Time complexity: O(N)
• Space complexity: O(N)