Feature #3: Traversing DOM Tree II
Implementing the "Traversing DOM Tree II" feature for our "Stock Scraper" project.
We'll cover the following
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 nullptr
. 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:
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.