Depth-First Search
And its use in the internet
Surely you’ve loaded a webpage before?
As you look at the webpage, you realise it has several components. Each component in the page has its own importance. The web browser loads these components to create the web page that you end up seeing.
Given all these components, you wonder how your web browser assembles them seamlessly into a display that looks good and gives you what you want to see. And so, you decide to investigate further…
In this article you’ll learn
what a tree is
how data is arranged hierarchically
and how the web uses it to display web-pages seamlessly to billions of viewers the world over.
Trees
You’ve seen trees before. But you need to recap a little bit, and also dive a little deeper. So here we go.
The best way to understand a tree is to construct it in real-time. Trees arrange data in a hierarchical manner. Data is stored in nodes. At the very top of the hierarchy is something called the root node. Every node has something called “children nodes”. Children nodes lower down in the hierarchy. Nodes are connected using edges.
These nodes then have their own children, even lower in the tree. You can think of it like a family tree. Children of children are called grandchildren, and their children are called grandchildren, and so on. But to simplify and generalise, the terminology is changed. Children of children are descendants, and parents of parents are ancestors.
Since the structure is hierarchical, we will eventually reach the very bottom. These final nodes are called leaf nodes.
Trees are useful when we want to arrange data as a hierarchy.
Armed with this new knowledge, you set off to start creating your first website.
HTML and the DOM
The elements in websites are designed using HTML. To start off, HTML can be used to make a simple website. Nothing fancy, just some text and a button that greets you when you click it.
If you copy-paste the above code into a web browser, you’ll just get a title that says “Click Me!” and alternates its colour between red and black if you click it.
Let’s walk through the steps taken to construct the web-page.
Step 1: Creating the hierarchy
Analysing the above code, you realise the strange indentation. Some elements are nested inside some other elements. Since the elements are arranged in a hierarchy, the best way to arrange this data is in a tree. To do this, we use the Document Object Model (DOM).
The Document Object Model (DOM) is exactly what sounds like. It uses a model to arrange the elements of the document as objects in a tree.
The browser parses the HTML first. In this step, it creates “tokens” in a process called “tokenisation”. Tokens contain a start tag, and end tag, content and attributes.
These tokens are what allow the HTML tags to be converted into elements in a tree. At the same time, another process is running called the “Preload scanner”. This process requests high-priority resources. This includes external links, CSS, JavaScript, and other content. This process runs so that no time is wasted later on in trying to obtain these resources, since it takes time.
A question pops up- why is this hierarchy needed? There are a few reasons for this.
A hierarchy allows data to be arranged neatly
A hierarchy creates an order in which the HTML elements can be processed
A hierarchy allows the nested elements to be represented neatly. The head contains different elements from the body, for example.
Another important element is the CSS. CSS is independent from the HTML to make it easier to add styles to the HTML elements by independently assigning them attributes. There isn’t really any CSS in our example web-page, but you can see it by inspecting the web-page from before.
The CSS is also arranged in a tree, and is processed simultaneously alongside the HTML. But we’ll not go through this in much detail for now.
Step 2: The Object Model Trees
There are 2 trees to construct, now that we know the hierarchy. One of these is the DOM (Document Object Model) tree, which we’ll focus on. The other, constructed simultaneously, is the CSSOM (CSS Object Model) tree.
To construct the DOM tree, you start from the root. At the very top of the hierarchy is the <html> element. Next, we look at the elements nested in html. At the 2nd level of indentation, you notice there’s 2 elements (head and body). So let’s add these to the DOM.
The DOM continues getting constructed. The next layer is added to the DOM after this.
This is how the hierarchy is represented by the web-page.
Note: The CSSOM tree is created simultaneously alongside the DOM tree. It is similar to the above, but is a tree for the hierarchy of CSS attributes given to elements. The CSSOM tree is separate from the DOM, but is not shown above because there isn’t any CSS in our code. The logic is the same, however.
Step 3: The render tree
In this step, the non-visual elements from the tree are removed. Information from the CSSOM tree is also considered to add styles to the elements, and the browser decides how to size and organise the various elements.
It’s important to notice a few things.
Head does not contain visual information. The render tree is for the page body. The head is not really important, except the title which can be dealt with separately
<html> and <body> are in the render tree only because they are parent nodes of <h3>, which is the only visual element in our simple web-page.
Information from the CSSOM tree, which contains further properties like font-size, etc, is all included in the render tree
Step 4: Constructing the web-page
There are 2 processes to understand here- repaint and reflow.
The first is the reflow. In a reflow, the browser re-calculates the positions of every element in the render tree on the page. The first reflow has already been carried out, when the browser calculated how to position elements in the render tree during construction. A reflow happens whenever the page is updated in a way that elements are resized or moved.
A repaint is when the browser needs to change things like opacity, colour, outline, etc. Basically, the browser is painting the elements onto the screen. This uses an algorithm called depth-first search (DFS).
The DFS algorithm processes the tree node-by-node in a specific order. It first starts of processing the current node. It then processes each child node. But because it is recursive, processing a child is the same as processing an entire branch (collection of nodes in a path from the root to a leaf) in the render tree. Since our current tree contains only one path (<html> → <body> → <h3>), we’ll imagine a more complicated tree like this one.
Pre-order DFS is called from the root.
Starting from the root, it moves to the next child. It processes the next child, and moves on to process each child of that node. The process continues till a leaf node is reached. The first path taken by pre-order DFS is shown here.
Once that’s done, it moves on to process the remaining child nodes of the current node. It reaches the 2nd leaf.
Now all the children of the first child of the root node have been traversed. So the algorithm moves on to the next child and repeats the process.
The code for this recursive process can be written in JavaScript.
DFS is used to repaint the page. For example, when we click the text to change its colour.
Modern browsers often use a compositing process to improve performance. In this step, painted elements are split into multiple layers. These layers can be independently manipulated and combined (composited) to form the final image that appears on the screen. Compositing allows for efficient handling of complex animations, transformations, and other visual effects by reducing the need to repaint the entire screen
In addition to the basic traversal, the browser must also handle stacking contexts correctly. Stacking contexts determine the order in which elements are painted, especially when elements overlap. Each stacking context is painted in the following order:
Background and Borders of the element forming the stacking context.
Negative Z-Index Children.
Normal Flow Children (non-positioned elements).
Floating Elements.
Positive Z-Index Children.
The Z-index is just a CSS value that can be given to determine the order in which elements are created. This ordering ensures that elements are painted in the correct order based on their z-index and stacking context
Final words
This explanation is a simplification of how different elements in the web works. So next time you see something complicated like this, you know how elements are arranged, and how to find them.
To summarise, you learnt what a tree is. You learnt how trees are traversed using DFS, and how this algorithm is implemented in the web to locate elements in web pages. You learnt the reason this hierarchy is needed to arrange elements and make it easier to construct and edit them.
Content with your learning, you decide to call it a day with some entertainment, the same entertainment that started this journey…
Thanks for reading! This article was a collaboration between
and . If you enjoy this content, check out our publications. We hope to see you around!
 | A guest post by
|
nice one!