Traversing the HTML DOM using depth and breath first search

The DOM forms the backbone of all web pages in the modern browsers. DOM stands for document object model meaning it represents the HTML document as an object that contains other objects like element nodes, text nodes, attribute nodes etc. The DOM is a tree data structure. It is similar to the commonly used binary tree but with a slight modification so that each parent can have more than 2 child nodes. This is called an N-Ary tree where each parent can have as many as N number of children. The HTML object nodes provide useful API to figure out the relationship between different nodes which can be used in traversal algorithms. Algorithms such as depth and breath first search can be used to traverse the DOM in a desired manner.

Fig 1.0 N-Ary Tree

DOM node APIs

• <node>.parentNode
• <node>.childNodes[<nodenumber>]
• <node>.firstChild
• <node>.lastChild
• <node>.nextSibling
• <node>.previousSibling

The above api methods can be used to get information about node relationships from DOM nodes. These nodes can be of any type like 'div' which is an element node or '<!--This is a comment-->' which is a comment node. Developers can find element nodes with particular id like 'document.getElementById('portfolio');' then the result will have all the api methods as listed above.

Depth First Search: Pre-Order Traversal

Pre-order traversal uses a stack to keep track of nodes and the output sequence will be A, B, G, M, N, H, I, C, D, E, J, O, K, P, F, G, L for Fig 1.0.

let dfsOnHTMLNodesPreOrder = (node = document.body) => {

	let stk = [];
	stk.push(node);

	while(stk.length !== 0){

		let currentNode = stk.pop();

		//check for the condiditon or just console.log
		console.log(currentNode);

		if(currentNode && currentNode.childNodes && currentNode.childNodes.length >0){

			for(let i = currentNode.childNodes.length - 1; i>=0; i--){
				stk.push(currentNode.childNodes[i]);
			}
		}
	}

}

In the above code we use JavaScript array as stack data structure. Then we push the argument node to the stack or push 'document.body' if no node is passed. Then we pop the stack and see if the node has any children. Then push all the children of the 'currentNode' to the stack from right to left. You can run this in developer console in Chrome by pasting the code and calling the method. The time and space complexity are O(n), where n is the number of nodes.

Breath First Search/Level-Order Traversal

Level order traversal allows developers to traverse level by level of the HTML DOM. As an example the output for N-Ary tree in Fig 1.0 would be A, B, C, D, E, F, G, G, H, I, J, K, L, M, N, O, P. The algorithm will use a queue data structure to keep track of nodes.

let bfsOnHTMLNodes = (node = document.body) => {

    let queue = [];
    queue.push(node);

    while (queue.length !== 0) {

        let currentNode = queue.shift();

        //check for the condiditon or just console.log
        console.log(currentNode);

        if (currentNode && currentNode.childNodes && currentNode.childNodes.length > 0) {

            for (let i = 0; i < currentNode.childNodes.length; i++) {
                queue.push(currentNode.childNodes[i]);
            }
        }
    }

}

In the algorithm we have used an array to replace the queue data structure. In the algorithm we initially add the argument node to the queue or add the 'document.body' node if no node is provided. Then the while loop is started on condition that the queue is not empty. Then the 'shift()' method is called which simulates the '.remove()' method for queue in Java. Then we check if it has any children then add all the children to the queue from left to right. You can run this algorithm in the Chrome developer console. The time and space complexity are O(n), where n is the number of nodes.