Implementing the DOM contains() method
Tags: javascript, uiweekly, algorithms, computerscience
Published: 2021-07-07 04:55:36

As per [MDN](https://developer.mozilla.org/en-US/docs/Web/API/Node/contains),

> The **Node.contains()** method returns a Boolean value indicating whether a node is a descendant of a given node, i.e. the node itself, one of its direct children (**childNodes**), one of the children's direct children, and so on.

But wait, `Node.prototype.contains(...)` already exists. I want another name for our custom function. Let's google synonym of `contains` coz 

![why not](https://media1.tenor.com/images/cb10e995344ad2efd30b118665968ec4/tenor.gif?itemid=13251824)

### Intense googling later......
 
![Screen Shot 2021-07-06 at 7.26.12 PM.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1625579876465/RdC5aInl8h.png)

Certainly we ain't going with **swallow**. I think **includes** would be cool as both `Array` and `String` have **includes** as well in their **prototypes**. 

![inclusion](https://media4.giphy.com/media/SVOVZaQynOVY5mA5WN/200.gif)

Before we proceed one important thing to know is that when adding new method to `prototype` and expecting to use it like so :-

 `document.includes(document.body)`, 

the **method** should not be an **arrow function** so that `document` can be accessed inside the `includes` function via `this` keyword. 

Alright then, let's implement `Node.prototype.includes` in 4 different ways :-

![four](https://media1.tenor.com/images/b8743c8e18e16e5b3eb2f9e93e3c2e86/tenor.gif?itemid=14057657)

### The recursive DFS

```js
1 Node.prototype.includes = function(node){
2 const currentNode = this;
3  if(!currentNode)
4   return false;
5  if(currentNode===node)
6   return true;
7  let isNodeFound = false;
8 for(let index = 0;index<currentNode.childNodes.length;index++){
9    isNodeFound = isNodeFound || currentNode.childNodes[index].includes(node);
10   if(isNodeFound) return true;
11  }
12  return false;
13 }
```

**Explanation :-**
* Line **2 to 4** - Set `currentNode` to `this` and If `currentNode` doesn't exist, simply return `false`.
* Line **5 to 6**  - if `currentNode` is equal to `node` return `true`.
* Line **7 to 13** -  Initialize `isNodeFound` to `false`. Then loop over `childNodes` of the `currentNode` and on each child, call the `includes` method again to check if they include the `node` element. If they do, `isNodeFound` will ultimately become `true` since it is being **Orrrrrrd** with the results coming from respective `childNodes` and reassigned to itself. Once `isNodeFound` is `true`, we don't need to loop over rest of the `childNodes` of `currentNode` and exit early by returning `true` else ultimately return `false`.

---

### The iterative BFS

```js
1 Node.prototype.includes = function (node) {
2 const queue = [];
3  let currentNode = this;
4  queue.push(currentNode);
5  while (queue.length) {
6    currentNode = queue.shift();
7    if (currentNode === node) return true;
8    if (currentNode.hasChildNodes()) {
9      queue.push(...currentNode.childNodes);
10    }
11 }
12  return false;
13 };
```

**Explanation :-**
* Line **2 to 4** - Initialize an empty list as `queue`. Set `currentNode` to `this` and `push` (or **enqueue** to be **specific**) it. 
* Line **5 to 12** - While the `queue` is **not empty**, **dequeue** the `currentNode` from front of the `queue` (using `shift` here). If `currentNode` is equal to `node` then return `true`. Otherwise **enqueue** the `childNodes` of `currentNode` (using `push` here). Once we are out of the `while` loop, we have traversed all the **nodes** and can safely say that we couldn't find the `node` and return `false`.

**Note - The above can be transformed to iterative DFS by using `pop` instead of `shift` and obviously for the sake of consistency, rename `queue` to `stack`.**

![nerd](https://media2.giphy.com/media/l1KVb2dUcmuGG4tby/200.gif)

Till now both the approaches followed the classic **DS/Algo** traversal with DFS and BFS. 
We are now going to see 2 more approaches which take benefit of certain properties that are specifically applicable to **DOM nodes**.

---

### LCRS (Left Child Right Sibling) [form](https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree)

```js
1 Node.prototype.includes = function (node) {
2 const currentNode = this;
3 if (!currentNode)
4   return false;
5 if (currentNode === node) return true;
6 return !!(currentNode.firstChild?.includes(node) || currentNode.nextSibling?.includes(node))
7 };
```
 **Explanation :-**
* Line **2 to 5** - 
   * Initialize `currentNode` to `this` and if `currentNode` doesn't exist, return `false`.
   * If `currentNode` is equal to `node` return `true`
* Line **6** - **DOM nodes** not only have pointers to their **childNodes** but also to their **sibling nodes** as well as **parent nodes**. Here we are going to leverage the **sibling factor** for easy traversal. So, we can now check whether the **current node's** `firstChild` includes the `node` **OR** **current node's** `nextSibling` includes the `node`. Also notice the `!!`. That's because I have used the `?` operator due to which we can end up with `undefined || undefined`  condition or `false || undefined` condition where both evaluate to `undefined` which is a **falsy** value and so `!!` will ensure `undefined` coerces to `false`. 

![sibling](https://media.tenor.com/images/5e88e1dee88940e7d3733039f2e67c1f/tenor.gif)

---

### Using parentNode

```js
1 Node.prototype.includes = function(node){
2 const currentNode = this;
3  while(node){
4    if(currentNode===node) return true;
5    node = node.parentNode;
6  }
7  return false;
8 }
```

**Explanation :-**
* Line **2 to 7** - Remember **DOM node** being so attached to it's siblings and parent ? The latter one works well for this use-case as well. While `node` exists, we check if `currentNode` is equal to `node` and if it is we return `true`, else the `node` is made to point to it's `parentNode` for further comparisons. If we exit the `while` loop, it's safe to say that the `node` isn't a contained within the `currentNode` and thus, return `false`.

![parent](https://media2.giphy.com/media/l41YaVemSbdw1yTTi/giphy.gif)

And here is a working codepen with all 4 implementations. Comment the rest for any one to reflect ✨.

{% codepen https://codepen.io/lapstjup/pen/ZEKQZRN %}

Have more ways to implement the same ? Feel free to share your approach in the comment section 👇.

### Thank you for your time :D