Skip to main content

DFS & BFS on HTML

// DFS Implementation for DOM traversal
function dfsTraversal(rootNode, callback) {
    if (!rootNode) return;
    
    // Process current node
    callback(rootNode);
    
    // Recursively process all child nodes
    const children = rootNode.children;
    for (let i = 0; i < children.length; i++) {
        dfsTraversal(children[i], callback);
    }
}

// BFS Implementation for DOM traversal
function bfsTraversal(rootNode, callback) {
    if (!rootNode) return;
    
    const queue = [rootNode];
    
    while (queue.length > 0) {
        const currentNode = queue.shift();
        callback(currentNode);
        
        // Add all children to queue
        const children = currentNode.children;
        for (let i = 0; i < children.length; i++) {
            queue.push(children[i]);
        }
    }
}

// Utility function to get element path
function getElementPath(element) {
    if (!element) return '';
    
    let path = element.tagName.toLowerCase();
    if (element.id) {
        path += `#${element.id}`;
    } else if (element.className) {
        path += `.${element.className.split(' ').join('.')}`;
    }
    return path;
}

// Example usage with practical applications

// 1. Find all elements with a specific class
function findElementsByClass(rootNode, className) {
    const results = [];
    
    bfsTraversal(rootNode, (node) => {
        if (node.classList && node.classList.contains(className)) {
            results.push(node);
        }
    });
    
    return results;
}

// 2. Create a DOM tree structure representation
function createDOMTree(rootNode) {
    let tree = '';
    let depth = 0;
    
    dfsTraversal(rootNode, (node) => {
        const indent = '  '.repeat(depth);
        tree += `${indent}${getElementPath(node)}\n`;
        depth++;
        
        // Decrease depth after processing all children
        setTimeout(() => depth--, 0);
    });
    
    return tree;
}

// 3. Find the deepest nested element
function findDeepestElement(rootNode) {
    let maxDepth = 0;
    let deepestElement = null;
    
    function dfsWithDepth(node, depth) {
        if (depth > maxDepth) {
            maxDepth = depth;
            deepestElement = node;
        }
        
        const children = node.children;
        for (let i = 0; i < children.length; i++) {
            dfsWithDepth(children[i], depth + 1);
        }
    }
    
    dfsWithDepth(rootNode, 0);
    return { element: deepestElement, depth: maxDepth };
}

// 4. Find all text nodes
function findTextNodes(rootNode) {
    const textNodes = [];
    
    function dfsText(node) {
        // Check for text nodes
        if (node.nodeType === 3 && node.textContent.trim().length > 0) {
            textNodes.push(node);
        }
        
        // Process child nodes
        for (let i = 0; i < node.childNodes.length; i++) {
            dfsText(node.childNodes[i]);
        }
    }
    
    dfsText(rootNode);
    return textNodes;
}

// 5. Calculate DOM tree metrics
function getDOMMetrics(rootNode) {
    let metrics = {
        totalElements: 0,
        maxDepth: 0,
        totalTextNodes: 0,
        elementTypes: {}
    };
    
    function dfsMetrics(node, depth) {
        metrics.totalElements++;
        metrics.maxDepth = Math.max(metrics.maxDepth, depth);
        
        // Count element types
        const tagName = node.tagName?.toLowerCase();
        if (tagName) {
            metrics.elementTypes[tagName] = (metrics.elementTypes[tagName] || 0) + 1;
        }
        
        // Count text nodes
        if (node.nodeType === 3 && node.textContent.trim().length > 0) {
            metrics.totalTextNodes++;
        }
        
        // Process children
        const children = node.childNodes;
        for (let i = 0; i < children.length; i++) {
            dfsMetrics(children[i], depth + 1);
        }
    }
    
    dfsMetrics(rootNode, 0);
    return metrics;
}

// Example Usage:
// HTML structure for testing
const sampleHTML = `
<div id="root">
    <header class="header">
        <nav>
            <ul>
                <li>Home</li>
                <li>About</li>
            </ul>
        </nav>
    </header>
    <main>
        <article>
            <h1>Title</h1>
            <p>Content</p>
        </article>
    </main>
</div>
`;

// Create a DOM parser for testing
const parser = new DOMParser();
const doc = parser.parseFromString(sampleHTML, 'text/html');
const root = doc.querySelector('#root');

// Test examples
console.log('DFS Traversal:');
dfsTraversal(root, node => {
    console.log(getElementPath(node));
});

console.log('\nBFS Traversal:');
bfsTraversal(root, node => {
    console.log(getElementPath(node));
});

console.log('\nDOM Tree Structure:');
console.log(createDOMTree(root));

console.log('\nDOM Metrics:');
console.log(getDOMMetrics(root));

// Find elements with class
const headerElements = findElementsByClass(root, 'header');
console.log('\nHeader Elements:', headerElements);

// Find deepest element
const deepest = findDeepestElement(root);
console.log('\nDeepest Element:', getElementPath(deepest.element), 'at depth:', deepest.depth);

// Find text nodes
const textNodes = findTextNodes(root);
console.log('\nText Nodes:', textNodes.map(node => node.textContent.trim()));

Find all descendants of a given element (DFS)​

Problem: Given an element in the DOM (e.g., a div), find all its descendant elements using DFS.

function findDescendantsDFS(element) {
    let result = [];
    function dfs(node) {
        if (!node) return;
        result.push(node);
        for (let child of node.children) {
            dfs(child);
        }
    }
    dfs(element);
    return result;
}

// Example usage
const root = document.getElementById('root');
console.log(findDescendantsDFS(root));

Find all ancestors of a given element (DFS)​

Problem: Given an element, find all its ancestor elements using DFS.

function findAncestorsDFS(element) {
    let result = [];
    function dfs(node) {
        if (!node) return;
        result.push(node);
        if (node.parentElement) {
            dfs(node.parentElement);
        }
    }
    dfs(element);
    return result.reverse(); // To list ancestors from root to the given element
}

// Example usage
const target = document.getElementById('targetElement');
console.log(findAncestorsDFS(target));

Level-order traversal of the DOM tree (BFS)​

Problem: Perform a level-order traversal (BFS) of the DOM tree starting from a given element.

function levelOrderTraversalBFS(element) {
    let result = [];
    let queue = [element];

    while (queue.length > 0) {
        let node = queue.shift();
        result.push(node);
        for (let child of node.children) {
            queue.push(child);
        }
    }

    return result;
}

// Example usage
const root = document.getElementById('root');
console.log(levelOrderTraversalBFS(root));

Find all siblings of a given element (BFS/DFS)​

Problem: Given an element, find all its sibling elements.

function findSiblingsBFS(element) {
    const parent = element.parentElement;
    if (!parent) return [];
    const siblings = [];
    for (let child of parent.children) {
        if (child !== element) {
            siblings.push(child);
        }
    }
    return siblings;
}

// Example usage
const target = document.getElementById('targetElement');
console.log(findSiblingsBFS(target));

Find all leaf nodes in the DOM (DFS)​

function findLeafNodesDFS(element) {
    let leafNodes = [];
    function dfs(node) {
        if (!node) return;
        if (node.children.length === 0) {
            leafNodes.push(node);
        }
        for (let child of node.children) {
            dfs(child);
        }
    }
    dfs(element);
    return leafNodes;
}

// Example usage
const root = document.getElementById('root');
console.log(findLeafNodesDFS(root));

Find the shortest path between two elements (BFS)​

Problem: Given two elements in the DOM, find the shortest path between them using BFS.

function findShortestPathBFS(start, end) {
    let visited = new Set();
    let queue = [[start]]; // Queue of paths

    while (queue.length > 0) {
        let path = queue.shift();
        let node = path[path.length - 1];

        if (node === end) return path;
        visited.add(node);

        for (let child of node.children) {
            if (!visited.has(child)) {
                queue.push([...path, child]);
            }
        }
    }
    return null; // No path found
}

// Example usage
const start = document.getElementById('startElement');
const end = document.getElementById('endElement');
console.log(findShortestPathBFS(start, end));

Detect cycles in the DOM (DFS)​

function hasCycleDFS(element) {
    let visited = new Set();

    function dfs(node) {
        if (!node) return false;
        if (visited.has(node)) return true;
        visited.add(node);

        for (let child of node.children) {
            if (dfs(child)) return true;
        }
        return false;
    }

    return dfs(element);
}

// Example usage
const root = document.getElementById('root');
console.log(hasCycleDFS(root));