Mastering DOM Traversal and Sorting: Recursive & Non‑Recursive JavaScript Algorithms

0 Introduction

As a front‑end engineer with a mathematics background, I discuss the necessity of understanding fundamental data‑structure and algorithm concepts when writing JavaScript for the browser.

1 Data Structures and Search Algorithms

1.1 Recursion

Recursion means a function calling itself; a classic use case is searching a DOM tree.

function getElementById(node, id){
    if(!node) return null;
    console.log(node.id);
    if(node.id === id) return node;
    for(var i = 0; i < node.childNodes.length; i++){
        var found = getElementById(node.childNodes[i], id);
        if(found) return found;
    }
    return null;
}
getElementById(document, "id-data-structure");

The algorithm performs a depth‑first search, which is simple and readable but less efficient because each traversal starts from the root and the function mixes traversal logic with search responsibility, violating the single‑responsibility principle.

1.2 Non‑Recursive Depth‑First Search

A non‑recursive version uses an explicit next‑node function to walk the DOM without recursion.

<div id="id-data-structure">
    I am body
</div>

function getElementById(node, id){
    while(node){
        if(node.id === id) return node;
        node = nextNode(node);
    }
    return null;
}
function nextNode(node){
    if(node.children.length) return node.children[0];
    if(node.nextElementSibling) return node.nextElementSibling;
    while(node.parentNode){
        if(node.parentNode.nextElementSibling) return node.parentNode.nextElementSibling;
        node = node.parentNode;
    }
    return null;
}
getElementById(document, "id-data-structure");

This approach also follows a depth‑first strategy and is similar to the algorithm used by Google’s V8 engine, which first builds a map of element IDs for O(1) lookup.

Map::iterator it = m_map.begin();
while(it != m_map.end()){
    LOG(INFO) << it->key << " " << it->value->element->tagName();
    ++it;
}

1.3 Hash Structures and Related Algorithms

Given an array of objects {picId, src}, we need to retrieve the src for a specific picId. Two approaches are shown: a reverse sequential search and a custom hash table implementation.

function sequentialSearch(sTable, targetPic){
    for(var i = sTable.length - 1; i >= 0 && sTable[i].id !== targetPic.id; --i);
    return sTable[i];
}

function Hashtable(){ this._hashValue = {}; }
Hashtable.prototype.add = function(inputArray){
    for(let i = 0; i < inputArray.length; i++){
        this._hashValue[inputArray[i]['key']] = inputArray[i]['value'];
    }
    return this._hashValue;
};
Hashtable.prototype.get = function(key){
    if(typeof key === 'string' && this._hashValue[key]){
        return this._hashValue[key];
    }
};
const createHash = new Hashtable();
createHash.add(picArray);
console.log(createHash.get('123')); // hhh

Hash tables store key‑value pairs, allowing constant‑time retrieval when the hash function distributes keys uniformly.

2 Sorting Algorithms and JavaScript Implementation

Sorting is a frequent front‑end requirement for displaying items by date, popularity, rating, price, etc. While servers can sort data, front‑end sorting can reduce backend load for large datasets.

2.1 Quick Sort (Out‑of‑Place)

const quickSort = arr => {
    if(arr.length <= 1) return arr;
    const pivotIndex = Math.floor(arr.length / 2);
    const pivot = arr.splice(pivotIndex, 1)[0];
    const left = [];
    const right = [];
    arr.forEach(item => {
        if(item < pivot) left.push(item);
        else right.push(item);
    });
    return quickSort(left).concat([pivot], quickSort(right));
};
function testTime(){
    console.time('classic sort');
    quickSort([20,44,23,55,77,19]);
    console.timeEnd('classic sort');
}
testTime();

This version creates new left and right arrays, giving O(n) extra space.

2.2 In‑Place Quick Sort with Improved Pivot Selection

function quickSort(arr){
    function swap(arr,a,b){ const t = arr[a]; arr[a]=arr[b]; arr[b]=t; }
    function partition(arr, low, high){
        let middle = low + Math.ceil((high - low) / 2);
        if(arr[low] > arr[high]) swap(arr, low, high);
        if(arr[middle] > arr[high]) swap(arr, high, middle);
        if(arr[middle] > arr[low]) swap(arr, middle, low);
        let pivot = arr[low];
        let i = low, j = high;
        while(i <= j){
            while(arr[j] >= pivot && i < j) j--;
            while(arr[i] <= pivot && i < j) i++;
            if(i < j) swap(arr, i, j);
        }
        swap(arr, low, i);
        return i;
    }
    function Qsort(arr, low, high){
        if(low < high){
            const p = partition(arr, low, high);
            Qsort(arr, low, p-1);
            Qsort(arr, p+1, high);
        }
    }
    Qsort(arr, 0, arr.length-1);
    return arr;
}
function testTime(){
    console.time('worst‑case quickSort');
    quickSort([20,44,23,55,77,19]);
    console.timeEnd('worst‑case quickSort');
}
testTime();

By choosing the median of low, middle, and high as the pivot, the algorithm avoids the O(n²) worst case and achieves O(log n) auxiliary space.

2.3 Merge Sort (Stable)

function merge(leftArr, rightArr){
    const result = [];
    while(leftArr.length && rightArr.length){
        if(leftArr[0] < rightArr[0]) result.push(leftArr.shift());
        else result.push(rightArr.shift());
    }
    return result.concat(leftArr).concat(rightArr);
}
function mergeSort(array){
    if(array.length === 1) return array;
    const middle = Math.floor(array.length/2);
    const left = array.slice(0, middle);
    const right = array.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
const arr = mergeSort([32,12,56,78,76,45,36]);
console.log(arr);
function testTime(){
    console.time('mergeSort');
    mergeSort([32,12,56,78,76,45,36]);
    console.timeEnd('mergeSort');
}
testTime();

Merge sort is stable and has O(n) space complexity, making it suitable when stability is required.

In practice, front‑end developers choose the algorithm that best fits the data size, stability requirements, and memory constraints; quick sort is fast but unstable, merge sort is stable but uses more memory, and insertion sort can be optimal for very small arrays.