Feature #3: Traversing DOM Tree II

Description

The technique we used previously to traverse through the web tree used too much space. The number of web pages can be enormous, and traversing all of them will consume a lot of unnecessary space. Therefore, we have come up with a better approach in which we create a shadow tree for the DOM where each node has a pointer to the next node to its right on the same level. We’ll introduce an additional attribute, next, to our TreeNode structure. The next node will point to its immediate right node on the same level. If there is no right node to point, next will be a nil. This next pointer will allow us to avoid the queue data structure that we used previously to traverse the tree, resulting in a space-efficient approach.

We’ll be provided with a root node of an n-ary tree. The root node in our case will again be the body tag. This root node will have the complete web page nested within its children. We have to go through each node and assign the next pointer to the node to its immediate right on the same level.

Let’s try to understand this better with an illustration: