Learn Data Structure and Algorithm in JavaScript | Part 15

Akanksha Sharma🚀

@akankshashar07

@DThompsonDev I struggled so much in learning linklist and trees concept that now I got really better with it(Still not an expert as programming has its way of surprising you). Trying hard with javascript concepts now but its even more stubborn than I am.

12:13 PM - 20 Aug 2020

0 1

Mauricio

@spaceinvadev

"We call a data structure a" tree" when it has a branching structure, has no cycles (a node may not be contain itself, directly or indirectly), and has a single, well-defined root."

#JavaScript #100DaysOfCode

15:55 PM - 25 Aug 2020

4 2

I Am Devloper

@iamdevloper

[zoom call]

Bob: hi everyone thanks for joining me, I just wanted to touch base with you all

Narrator: this is Bob. Bob hasn’t done anything all day, but for the sake of business optics, he’s gathered everyone together to give himself Busywork™️

18:53 PM - 13 Aug 2020

428 2813

Prerequisite (✋😐)

If you're reading this article right now, please considered to read our Part 01: Big-O Notation, Part 02: JavaScript Unique Part, Part 03: JavaScript Numbers to Part 14: Caching

Part	Table of Contents	Description
01	Big-O Notation	By the end of this chapter, you will understand how to analyze an implementation of an algorithm with respect to both time (execution time) and space (memory consumed).
02	JavaScript Unique Parts	Big-O is important for analyzing and comparing the efficiencies of algorithms. The analysis of Big-O starts by looking at the code, and, applying the rules, applying the rules is because to simplify the Big-O notation linear or quadratic rule is not enough.
03	JavaScript Numbers	This part 3 will focus on JavaScript number operations, number representation, Number objects, common number algorithms, and random number generation.
04	JavaScript Strings	This part 4 will focus on strings, JavaScript String object, and the String object’s built-in functions. You will learn how to access, compare, decompose, and search strings for commonly used real-life purposes. In addition, the chapter will explore string encoding, decoding, encryption, and decryption.
05	JavaScript Arrays	As a JavaScript developer, you will use the array often; it is the most commonly used data structure. Arrays in JavaScript come with a lot of built-in methods. By the end of this part, you will understand arrays and choose the right method
06	JavaScript Object	This part will focus on what JavaScript objects are, how they are declared, and how their properties can be changed. In addition, this part will cover how JavaScript classes are implemented using prototypal inheritance. Also this part will be short.
07	JavaScript Memory Management	A variable takes up some memory. In C, the programmer allocate and deallocate memory manually. In contrast, modern JavaScript engines have garbage collectors that delete unused variables. However, there are pitfalls(unexpected) that developers can fall into(❗) This part will show these unexpected and present techniques to help the garbage collector minimize the memory problems.
08	Recursion	This part 8 introduces the concept of recursion and recursive algorithms(Remember they are different, we will discuss them later(😉)). We will also discuss the definition of recursion and fundamental rules for recursive algorithms.
09	Sets	This part focuses on the concepts of sets from both a mathematical definition and on the implementation. Also, Common set operations, as well as their implementations, are covered in great detail (💡).
10	Searching and Sorting	This part 10 focuses on searching and sorting for arrays. By the end of this part 10, you will understand how to use sorting and searching algorithms for arrays. Also, this article is a bit complicated for beginners, so as much as possible the visual aids is your friend (👀). (😃)
11	Hash Tables	A hash table is a fixed-sized data structure in which the size is defined at the start. This part 11 explains how hash tables work, and the method of generating a unique key. By the end of this part 11, you will understand various hashing techniques and know how to implement a hash table. (😃)
12	Stacks and Queues	This part 12 covers stacks and queues(pronounce as kyooz (🔈)) not (kwewe) okay? hehehe (😅); both are data structures used in the implementation of complex data structures. You'll learn what the stacks and queues are, how they're used, when they're used, and how to implement them (😃) Let's go! (🔥🔥🔥)
13	Linked Lists	A linked list is a data structure in which each node (or element) points to another node. Unlike arrays, which have a fixed size, a linked list is a dynamic data structure. By the end of this part 13, you will understand how to implement and work with linked lists. And oh! (😮) There are two types of linked lists: singly (➡️) and doubly (↔️). Let’s examine the singly linked list first.(😃) Let's go! (🔥🔥🔥)
14	Caching	Caching is the process of storing data into temporary memory so that it can be easily retrieved for later use if it is required again. As an example, a database keeps data cached to avoid re-reading the hard drive, and a web browser caches web images to avoid re-downloading. In this part 14, two caching techniques will discussed: LFU and LRU caching.
15	Trees	A general tree data structure is composed of nodes with children nodes. The top node is called the root node. This part 15 will explore different types of trees such as binary trees, binary search trees, and self-balancing binary search trees. First, this part 15 will cover what trees are and how they are structured. Then, it will cover methods of traversing(crossing or taking a zigzag path) the tree data structure in detail. Finally, you will learn about binary search trees and self-balancing binary search trees to understand how to store searchable data. (😃)
16	Heaps	A heap is an important data structure that returns the highest or lowest element in O(1) time. This part 16 will focus on explaining how heaps are implemented as well as how to work with them. One example is heap sort, which is a sorting algorithm based on heaps.
17	Graphs	In this Part 17, you will learn graph basics, including fundamental terminology and graph types. The Part 17 will also cover working with these different graph types and methods of representing graphs in data structures. Finally, algorithms for traversing, searching, and sorting graphs are explored to solve problems such as finding the shortest path between two graph nodes. (👍)
18	Advance Strings	Part 18 will cover more complex string algorithms than covered in the previous section. Now that you have heard of certain other data models or structures, they should be easier to comprehend. Specifically, Part 18 will focus on string searching algorithms. (😉)
19	Dynamic Programming	Dynamic programming involves breaking down problems into their subproblems. Solving the subproblems and saving those results into memory to access them whenever a repeated problem needs to be solved, the algorithmic complexity decreases significantly (⬇️). To explain dynamic programming, let’s re examine the Fibonacci sequence that was discussed in Part 8. Then Part 19 will cover the rules of dynamic programming and walk you through some examples to make the concepts more concrete. (😉)
20	Bit Manipulation	Bit manipulation is an advanced topic that JavaScript developers typically do not need to know. However, you should learn a bit about bit manipulation if you want to implement high-performance server-side code. Understanding bit manipulation requires some knowledge of digital logic. Any introductory course in discrete math or circuits would be helpful to understand these concepts.

Part 15: Trees (😱 🔥 🌱)

A general tree data structure is composed of nodes with children nodes. The top node is called the root node. This part 15 will explore different types of trees such as binary trees, binary search trees, and self-balancing binary search trees. First, this part 15 will cover what trees are and how they are structured. Then, it will cover methods of traversing(crossing or taking a zigzag path) the tree data structure in detail. Finally, you will learn about binary search trees and self-balancing binary search trees to understand how to store searchable data. (😃)

Reminder (💡): You do not need to understand the code in detail discussed here, instead, learn the concept in mind, because the code may be forgotten, but the concept will remain in the subconscious mind. (😉)

General Tree Structure (📖🌱)

A general tree data structure like Figure 15-1 can have any number of children.

Figure 15-1. Generalized tree with any number of children

The code block for the node in the Figure 15-1 (above) tree is as follows:

// General Tree Strucutre: Tree Node
function TreeNode(value) {
    this.value = value;
    this.children = [];
}

Binary Trees (🔢🌱)

A binary tree is a type of tree that has only two children nodes: left and right as show in below:

Figure 15-2. Binary tree

See the following code and Figure 15-2 (above) just below:

// Binary Tree Structure: Tree Node
function BinaryTreeNode(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

A binary tree always has a root node (the node at the top), which is initialized to null before any element is inserted as shown in the example below:

// Binary Tree
function BinaryTree() {
    this._root = null;
}

Tree Traversal (🌱❌)

Traversal through an array is simple: you access the index and increment the index until the index reaches the size limit. But with trees, the left and right pointers have to be followed in order to go through every element in the tree. There are various ways to do this, the most popular traversal techniques are: pre-order traversal, post-order traversal, in-order traversal, and level-order traversal.

Pre-Order Traversal (➡️📦❌)

Pre-order traversal visits nodes in the following order: (1️⃣) root, (2️⃣) left, and (3️⃣) right. In Figure 15-3, you can see that 42 is the root, so it’s visited first. Then it goes left; at this point, the left of the parent 41 is now considered the new root. Then it goes left again to 10. So, 10 is set to the new root. Then 40 is visited because that is the right of the parent 41. This process continues, and the whole order is denoted by the gray squares in Figure 15-3:

Figure 15-3. Pre-order traversal

Recursively, this is implemented easily. The base case terminates when the node is null. Otherwise, it prints the node value and then calls the recursive function on its left child and then its right child:

// Binary Tree
function BinaryTree() {
    this._root = null;
}

// Pre-Order Traversal: Recursive
BinaryTree.prototype.traversePreOrderRecursive = function () {
    traversePreOrderHelper(this._root);

    function traversePreOrderHelper(node) {
        if(!node) return;

        console.log(node.value);
        traversePreOrderHelper(node.left);
        traversePreOrderHelper(node.right);
    }
}

This can also be done iteratively, but it is harder to implement:

// Binary Tree Structure: Tree Node
function BinaryTreeNode(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

// Binary Tree
function BinaryTree() {
    this._root = null;
}

// Pre-Order Traversal: Iterative
BinaryTree.prototype.traversePreOrderIterative = function () {
    // Create new empty stack and push the root to it.
    var nodeStack = [];
    nodeStack.push(this._root);

    // Pop all items one by one. 
    // Do the following for every popped item:
    //  a) Print it
    //  b) Push its right child
    //  c) Push its left child
    // Note: Right child is pushed first...
    // ...so that left is processed first

    while (nodeStack.length) {
        // Pop the top item from the stack and print it
        // We use push earlier...
        // ...so that means the first added element...
        // ...is at the last of the stack
        // So that means, Pop the top item...
        // ...from the stack

        var node = nodeStack.pop();
        console.log(node.value);
        // Push right and left children...
        // ... of the popped node to stack
        // Note: Right child is pushed first...
        // ...so that left is processed first
        // We'll see that below:

        // Right
        if (node.right)
            nodeStack.push(node.right);

        // Left
        if (node.left)
            nodeStack.push(node.left);

    }
}

Here is the result: $[ \space 42, \space 41, \space 10, \space 40, \space 50, \space 45, \space 75 \space]$

In-Order Traversal (📦➡️❌)

In-order traversal visits nodes in the following order: (1️⃣) left, (2️⃣) root (current node), (3️⃣) right

Figure 15-4. In-order traversal

In-order traversal is also implemented easily with recursion. The base case is when a node is null. It calls the recursive function on the left child, prints the current node, and then calls the recursive function on the right child:

// Binary Tree
function BinaryTree() {
    this._root = null;
}

// In-Order Traversal: Recursive
BinaryTree.prototype.traverseInOrderRecursive = function () {
    traverseInOrderHelper(this._root);

    function traverseInOrderHelper(node) {
        if (!node) return;

        traverseInOrderHelper(node.left);
        console.log(node.value);
        traverseInOrderHelper(node.right);
    }
}

This can also be done iteratively:

// Binary Tree
function BinaryTree() {
    this._root = null;
}

// In-Order Traversal: Iterative
BinaryTree.prototype.traverseInOrderIterative = function () {
    var current = this._root,
        s = [],
        done = false;

    while (!done) {
        // Reach the left most node of the current node
        if (current != null) {
            // Place pointer to a tree node on the stack
            // before traversing the node's left subtree
            s.push(current);
            current = current.left;
        } else {
            if (s.length) {
                current = s.pop();
                console.log(current.value);
                current = current.right;
            } else {
                done = true;
            }
        }
    }
}

Here is the result of this traversal: $[ \space 10, \space 41, \space 40, \space 42, \space 45, \space 50, \space 75 \space ]$

Post-Order Traversal (❌📦➡️)

Post-order traversal visits nodes in the following order: (1️⃣) left, (2️⃣) right, (3️⃣) root. For the tree shown in Figure 15-5, the gray squares indicate the in-order traversal. As you can see, 10 is printed first, and 42 is printed last:

Figure 15-5. Post-order traversal

Here’s the code:

// Binary Tree
function BinaryTree() {
    this._root = null;
}

// Post-Order Traversal: Recursive
BinaryTree.prototype.traversePostOrderRecursive = function () {
    traversePostOrderHelper(this._root);

    function traversePostOrderHelper(node) {
        if (node.left)
            traversePostOrderHelper(node.left);
        if (node.right)
            traversePostOrderHelper(node.right);
        console.log(node.value);
    }
}

This can also be done iteratively:

// Binary Tree
function BinaryTree() {
    this._root = null;
}

// Post-Order Traversal: Iterative
BinaryTree.prototype.traversePostOrderIterative = function () {
    // Create two stacks
    var s1 = [],
        s2 = [];

    // Push root to first stack
    s1.push(this._root);

    // Run while first stack is not empty
    while (s1.length) {
        // Pop an item from s1 and append it to s2
        var node = s1.pop();
        s2.push(node);

        // Pust left and right children of removed item to s1
        if (node.left)
            s1.push(node.left);

        if (node.right)
            s1.push(node.right);
    }

    // Print all elements of second stack
    while (s2.length) {
        var node = s2.pop();
        console.log(node.value);
    }
}

Here is the result: $[ \space 10, \space 40, \space 41, \space 45, \space 75, \space 50, \space 42\space ]$

Level-Order Traversal (➡️📏❌)

Level-order traversal is also known as breadth first search (BFS):

Figure 15-6. Level-order traversal

More of this will be covered in Part 17: Graphs, but this method visits each node level by level:

// Binary Tree
function BinaryTree() {
    this._root = null;
}

// Level-Order Traversal
BinaryTree.prototype.traverseLevelOrder = function () {
    // Breath first search
    var root = this._root,
        queue = [];

    if (!root) return;
    queue.push(root);

    while (queue.length) {
        var temp = queue.shift();
        console.log(temp.value);

        if (temp.left)
            queue.push(temp.left);

        if (temp.right)
            queue.push(temp.right);
    }
}

Here is the result: $[ \space 42, \space 41, \space 50, \space 10, \space 40,\space 45, \space 75 \space ]$

Tree Traversal Summary (🌱❌📚)

If you need to explore the roots before leaves, choose pre-order
traversal because you will encounter all the roots before all the leaves (🍃). If you need to explore all the leaves before any nodes, choose post-order traversal because you don’t waste any time inspecting roots when searching for leaves (🍃). If you want to flatten the tree into its original sequence, then you should use an in-order traversal. The tree would be flattened in the same way it was created. A pre-order or post-order traversal might not unwind the tree back into the sequence that was used to create it.

Time Complexity: $O \lparen n \rparen$

The time complexity of any of these traversals is the same because each traversal requires that all nodes are visited.

Binary Search Trees (🔎🌱)

Binary search trees (BSTs) also have two children, left and right. However, in a binary search tree, the left child is smaller than the parent, and the right child is bigger than the parent. BSTs have this structure because this enables searching, inserting, and removing specific values with $O \lparen log_{2} \lparen n \rparen \rparen$ time complexity.

Figure 15-7 (below) shows the BST. 1 is smaller than 2, so it is the left child of 2, and since 3 is bigger than 3, it is the right child of 2.

Figure 15-7. Binary search tree

Binary search trees have a root node, which is originally initialized null (before any item is inserted):

// Binary Search Tree
function BinarySearchTree() {
    this._root = null;
}

Figure 15-7 (above) also shows a balanced binary search tree where the height is minimized by having children on both the left and right sides. However, Figure 15-8 shows an unbalanced tree where children are only to the right of the parent. This has impact on the data structure and increases the time complexity of insertion, deletion, and search from $O \lparen log_{2} \lparen n \rparen \rparen$ to $O \lparen n \rparen$ . The perfect balanced tree is $log_{2} \lparen n \rparen$ , while an unbalanced tree can be $n$ in the worst case:

Figure 15-8. Unbalanced binary search tree

Insertion (➡️🌱⬅️)

Inserting into the BST requires a couple of steps. First, if the root is empty, the root becomes the new node. Otherwise, a while loop is used to traverse the BST until the right condition is met. At each iteration, it is checked whether the new node is greater or smaller than the currentRoot:

// Binary Search Tree
function BinarySearchTree() {
    this._root = null;
}

// Insert
BinarySearchTree.prototype.insert = function (value) {
    var thisNode = { left: null, right: null, value: value };

    if (!this._root) {
        // if there is no root value yet
        this._root = thisNode;
    } else {
        // loop traverse until...
        //... the right condition is met
        var currentRoot = this._root;
        while (true) {
            if (currentRoot.value > value) {
                // Let's increment if it's...
                // ...not a null and insert if...
                // ...it is a null
                if (currentRoot.left != null) {
                    currentRoot = currentRoot.left;
                } else {
                    currentRoot.left = thisNode;
                    break;
                }
            } else if (currentRoot.value < value) {
                // if bigger than current, put it on the right
                // Let's increment if it's...
                // ...not a null and insert if...
                // ...it is a null
                if (currentRoot.right != null) {
                    currentRoot = currentRoot.right;
                } else {
                    currentRoot.right = thisNode;
                    break;
                }
            } else {
                // In case that both are the same, break it
                break;
            }
        }
    }
}

Time Complexity (for balanced trees): $O \lparen log_{2} \lparen n \rparen \rparen$
Time Complexity (for unbalanced trees): $O \lparen n \rparen$

Note (📝): Time complexity is dependent on the height (top) of the binary search tree.

Deletion (❌🌱❌)

This algorithm works by first traversing down the tree looking for the node with the specified value. When the node is found, there are three possible cases:

• Case 1: The node has no children If the node has no child, return null. That node has been deleted now.
• Case 2: The node has one child If the node has one child, simply return the existing child. That child has now bubbled up and replaced the parent.
• Case 3: The node has two children If the node has two children, either find the maximum of the left or find the minimum of the right to replace that node.

The following code (below) implements the described three cases. First, it traverses recursively until one of those cases is met, and then the node is removed:

// Binary Search Tree
function BinarySearchTree() {
    this._root = null;
}

// Remove
BinarySearchTree.prototype.remove = function (value) {

    return deleteRecursively(this._root, value);

    function deleteRecursively(root, value) {
        if (!root) {
            return null;
        } else if (value < root.value) {
            root.left = deleteRecursively(root.left, value);
        } else if (value > root.value) {
            root.right = deleteRecursively(root.right, value);
        } else {
            // No child
            if (!root.left && !root.right) {
                // Case 1:
                return null;
            } else if (!root.left) {
                // Case 2:
                root = root.right;
                return root;
            } else if (!root.right) {
                // Case 2:
                root = root.left;
                return root;
            } else {
                // Case 3:
                var temp = findMin(root.right);
                root.value = temp.value;
                root.right = deleteRecursively(root.right, temp.value);
                return root;
            }
        }
        return root;
    }

    function findMin(root){
        while (root.left) {
            root = root.left;
        }
        return root;
    }
}

Time Complexity (for balanced tree): $O \lparen log_{2} \lparen n \rparen \rparen$
Time Complexity (for unbalanced trees): $O \lparen n \rparen$
Time complexity for deletion is also $O \lparen log_{2} \lparen n \rparen \rparen$ because at most, the height (top or vertical dimension) need to be traversed to find and delete the desired node.

Search (🔎🌱🔍)

Search can be performed using the property that BST node’s left child is always smaller than its parent and that BST node’s right child is always greater than its parent. Traversing the tree can be done by checking whether currentRoot is smaller or greater than the value to be searched. If currentRoot is smaller, the right child is visited. If currentRoot is bigger, the left child is visited.

Example:

// Binary Search Tree
function BinarySearchTree() {
    this._root = null;
}

// Insert

BinarySearchTree.prototype.insert = function (value) {
    var thisNode = { left: null, right: null, value: value };

    if (!this._root) {
        // if there is no root value yet
        this._root = thisNode;
    } else {
        // loop traverse until...
        //... the right condition is met
        var currentRoot = this._root;
        while (true) {
            if (currentRoot.value > value) {
                // Let's increment if it's...
                // ...not a null and insert if...
                // ...it is a null
                if (currentRoot.left != null) {
                    currentRoot = currentRoot.left;
                } else {
                    currentRoot.left = thisNode;
                    break;
                }
            } else if (currentRoot.value < value) {
                // if bigger than current, put it on the right
                // Let's increment if it's...
                // ...not a null and insert if...
                // ...it is a null
                if (currentRoot.right != null) {
                    currentRoot = currentRoot.right;
                } else {
                    currentRoot.right = thisNode;
                    break;
                }
            } else {
                // In case that both are the same, break it
                break;
            }
        }
    }
}

// Search
BinarySearchTree.prototype.findNode = function (value) {
    var currentRoot = this._root,
        found = false;

    while (currentRoot) {
        if (currentRoot.value > value) {
            currentRoot = currentRoot.left;
        } else if (currentRoot.value < value) {
            currentRoot = currentRoot.right;
        } else {
            // We've found the node
            found = true;
            break;
        }
    }

    return found;
}

// Instance of the Binary Search Tree class
var bst = new BinarySearchTree();

// Insert
bst.insert(1); // Add 1
bst.insert(2); // Add 2
bst.insert(3); // Add 3

// Search
console.log(bst.findNode(3)); // Prints "true"
console.log(bst.findNode(4)); // Prints "false"

Execution:

// Binary Search Tree function BinarySearchTree() { this._root = null; } // Insert BinarySearchTree.prototype.insert = function (value) { var thisNode = { left: null, right: null, value: value }; if (!this._root) { // if there is no root value yet this._root = thisNode; } else { // loop traverse until... //... the right condition is met var currentRoot = this._root; while (true) { if (currentRoot.value > value) { // Let's increment if it's... // ...not a null and insert if... // ...it is a null if (currentRoot.left != null) { currentRoot = currentRoot.left; } else { currentRoot.left = thisNode; break; } } else if (currentRoot.value < value) { // if bigger than current, put it on the right // Let's increment if it's... // ...not a null and insert if... // ...it is a null if (currentRoot.right != null) { currentRoot = currentRoot.right; } else { currentRoot.right = thisNode; break; } } else { // In case that both are the same, break it break; } } } } // Search BinarySearchTree.prototype.findNode = function (value) { var currentRoot = this._root, found = false; while (currentRoot) { if (currentRoot.value > value) { currentRoot = currentRoot.left; } else if (currentRoot.value < value) { currentRoot = currentRoot.right; } else { // We've found the node found = true; break; } } return found; } // Instance of the Binary Search Tree class var bst = new BinarySearchTree(); // Insert bst.insert(1); // Add 1 bst.insert(2); // Add 2 bst.insert(3); // Add 3 // Search console.log(bst.findNode(3)); // Prints "true" bst.findNode(4); // Prints "false"

Time Complexity (for balanced tree): $O \lparen log_{2} \lparen n \rparen \rparen$
Time Complexity (for unbalanced trees): $O \lparen n \rparen$

Note (📝): With unbalanced binary search trees, the time complexity is high. To address this, there are families of binary search trees that ensure the height is balanced. One example of such self-balancing trees is an AVL tree which we will discuss below. Let's go! (🔥🔥🔥)

AVL Trees (📐🌱)

AVL is a binary search tree that balances itself; it’s named after the inventors Georgy Adelson-Velsky (See on Wikipedia) and Evgenii Landis (See on Wikipedia). An AVL tree keeps the BST height to a minimum and ensures $O \lparen log_{2} \lparen n \rparen \rparen$ time complexities for search, insertion, and deletion. In previous examples, we defined both TreeNode and a Tree class and set the root of Tree as a TreeNode class. However, for the AVL tree implementation, only the AVLTree class, which represents the node of the AVL tree, will be used for the simplification of the code:

// AVL Tree
function AVLTree (value) {
    this.left = null;
    this.right = null;
    this.value = value;
    this.depth = 1;
}

The height of the AVL tree is based on the height of the children and can be calculated using the following code block:

// AVL Tree
function AVLTree(value) {
    this.left = null;
    this.right = null;
    this.value = value;
    this.depth = 1;
}

// Set Depth Based On Children
AVLTree.prototype.setDepthBasedOnChildren = function () {

    if (this.node == null) {
        this.depth = 1;
    }

    if (this.left != null) {
        this.depth = this.left.depth + 1;
    }

    if (this.right != null && this.depth <= this.right.depth) {
        this.depth = this.right.depth + 1;
    }
}

Single Rotation (🔄1️⃣🔄)

AVL trees rotate their children to maintain balance after insertion.

Rotate Left (1️⃣↩️1️⃣↩️)

Here is an example of when a node has to rotate left. Node 40’s children, the 45 and 47 nodes, cause the height to be unbalanced, as shown in Figure 15-9 (below). The 45 becomes the parent node in Figure 15-10 (below) to balance the BST:

Figure 15-9. Rotate left before

Figure 15-10. Rotate left after

To perform a left rotation, first get the right child (45) and store it. This is the “original” right child. The original right child is to be the parent of the node now. Set the node’s left child (40) to be the original right child’s (45) left child. Finally, set the original right child (45) to be the node (or parent node):

// AVL Tree
function AVLTree(value) {
    this.left = null;
    this.right = null;
    this.value = value;
    this.depth = 1;
}

// Set Depth Based On Children
AVLTree.prototype.setDepthBasedOnChildren = function () {

    if (this.node == null) {
        this.depth = 0;
    } else {
        this.depth = 1;
    }

    if (this.left != null) {
        this.depth = this.left.depth + 1;
    }

    if (this.right != null && this.depth <= this.right.depth) {
        this.depth = this.right.depth + 1;
    }
}

// Rotate Left
AVLTree.prototype.rotateLL = function () {

    var valueBefore = this.value;
    var rightBefore = this.right;
    this.value = this.left.value;

    this.right = this.left;
    this.left = this.left.left;
    this.right.left = this.right.right;
    this.right.right = rightBefore;
    this.right.value = valueBefore;

    this.right.setDepthBasedOnChildren();
    this.setDepthBasedOnChildren();
}

Rotate Right (1️⃣↪️1️⃣↪️)

Here is an example of when a node has to rotate right. 60’s children, the 55 and 52 nodes, cause the height to be unbalanced, as shown in Figure 15-11. The 55 node becomes the parent in Figure 15-12 to balance the BST:

Figure 15-11. Rotate right before

Figure 15-12. Rotate right after

To implement this algorithm, first get the left child (55) and store it. This the original left child. The original left child (55) is to be the parent of the node now. Set the node’s right child (60) to be the original left child’s right child. Finally, set the right child (55) to be the node (or parent node):

// AVL Tree
function AVLTree(value) {
    this.left = null;
    this.right = null;
    this.value = value;
    this.depth = 1;
}

// Set Depth Based On Children
AVLTree.prototype.setDepthBasedOnChildren = function () {

    if (this.node == null) {
        this.depth = 0;
    } else {
        this.depth = 1;
    }

    if (this.left != null) {
        this.depth = this.left.depth + 1;
    }

    if (this.right != null && this.depth <= this.right.depth) {
        this.depth = this.right.depth + 1;
    }
}

// Rotate Right
AVLTree.prototype.rotateRR = function () {
    // The right side is too long => rotate from the right
    // (_not_rightwards)
    var valueBefore = this.value;
    var leftBefore = this.left;
    this.value = this.right.value;

    this.left = this.right;
    this.right = this.right.right;
    this.left.right = this.left.left;
    this.left.left = leftBefore;
    this.left.value = valueBefore;

    this.left.setDepthBasedOnChildren();
    this.setDepthBasedOnChildren();
}

Double Rotation (🔄2️⃣🔄)

If an AVL tree is still unbalanced after one rotation, it has to rotate twice for full balance.

Rotate Right And Then Left (2️⃣↪️2️⃣↩️)

In this example, Figure 15-13 (below) shows a BST where the height is $3$ . By rotating right and then left, as shown in Figure 15-14 (below) and Figure 15-15 (below), balance is achieved:

Figure 15-13. A situation where rotating right and then rotating left is appropriate

Figure 15-14. Rotate right first

Figure 15-15. Rotate left after

Rotate Left And Then Right (2️⃣↩️2️⃣↪️)

Similarly, Figure 15-16 shows a BST where the height is $3$ . By rotating left and then right, as shown in Figure 15-17 and Figure 15-18, balance is achieved:

Figure 15-16. A situation where rotating left and then rotating right is appropriate

Figure 15-17. Rotate left first

Figure 15-18. Rotate right after

Balancing the tree (📐🌱📐)

To check for balance of the AVL tree, it is a simple comparison of the left and right children’s heights. When left is bigger than right, left rotation is done. When right is bigger than left, right rotation is done:

// AVL Tree
function AVLTree(value) {
    this.left = null;
    this.right = null;
    this.value = value;
    this.depth = 1;
}

// Rotate Right
AVLTree.prototype.rotateRR = function () {
    // The right side is too long => rotate from the right
    // (_not_rightwards)
    var valueBefore = this.value;
    var leftBefore = this.left;
    this.value = this.right.value;

    this.left = this.right;
    this.right = this.right.right;
    this.left.right = this.left.left;
    this.left.left = leftBefore;
    this.left.value = valueBefore;

    this.left.updateInNewLocation();
    this.updateInNewLocation();
}

// Rotate Left
AVLTree.prototype.rotateLL = function () {

    var valueBefore = this.value;
    var rightBefore = this.right;
    this.value = this.left.value;

    this.right = this.left;
    this.left = this.left.left;
    this.right.left = this.right.right;
    this.right.right = rightBefore;
    this.right.value = valueBefore;

    this.right.getDepthFromChildren();
    this.getDepthFromChildren();
}

// Balance
AVLTree.prototype.balance = function () {
    var ldepth = this.left == null ? 0 : this.left.depth;
    var rdepth = this.right == null ? 0 : this.right.depth;

    if (ldepth > rdepth + 1) {
        // RR or LL rotation
        var lldepth = this.left.left == null ? 0 : this.left.left.depth;
        var lrdepth = this.left.right == null ? 0 : this.left.right.depth;

        if (lldepth < lrdepth) {
            // LR Rotation consists of a RR rotation of the left child
            this.left.rotateRR();
            // Plus a LL rotation of this node, which happens anyway
        }
        this.rotateLL();
    } else if (ldepth + 1 < rdepth) {
        // RR or RL rotation
        var rrdepth = this.right.right == null ? 0 : this.right.right.depth;
        var rldepth = this.right.left == null ? 0 : this.right.left.depth;

        if (rldepth > rrdepth) {
            // RR rotation consists of a LL rotation of the right child
            this.right.rotateLL();
            // Plus a RR rotation of this node, which happens anyway
        }
        this.rotateRR();
    }
}

Insertion (➡️🌱⬅️)

Insertion in AVL BST is the same as the insertion in normal BST except that, once inserted, the parent must balance its children and set the right depth:

// AVL Tree
function AVLTree(value) {
    this.left = null;
    this.right = null;
    this.value = value;
    this.depth = 1;
}

// Set Depth Based On Children
AVLTree.prototype.setDepthBasedOnChildren = function () {

    if (this.node == null) {
        this.depth = 0;
    } else {
        this.depth = 1;
    }

    if (this.left != null) {
        this.depth = this.left.depth + 1;
    }

    if (this.right != null && this.depth <= this.right.depth) {
        this.depth = this.right.depth + 1;
    }
}

// Rotate Right
AVLTree.prototype.rotateRR = function () {
    // The right side is too long => rotate from the right
    // (_not_rightwards)
    var valueBefore = this.value;
    var leftBefore = this.left;
    this.value = this.right.value;

    this.left = this.right;
    this.right = this.right.right;
    this.left.right = this.left.left;
    this.left.left = leftBefore;
    this.left.value = valueBefore;

    this.left.updateInNewLocation();
    this.updateInNewLocation();
}

// Rotate Left
AVLTree.prototype.rotateLL = function () {

    var valueBefore = this.value;
    var rightBefore = this.right;
    this.value = this.left.value;

    this.right = this.left;
    this.left = this.left.left;
    this.right.left = this.right.right;
    this.right.right = rightBefore;
    this.right.value = valueBefore;

    this.right.getDepthFromChildren();
    this.getDepthFromChildren();
}

// Balance
AVLTree.prototype.balance = function () {
    var ldepth = this.left == null ? 0 : this.left.depth;
    var rdepth = this.right == null ? 0 : this.right.depth;

    if (ldepth > rdepth + 1) {
        // RR or LL rotation
        var lldepth = this.left.left == null ? 0 : this.left.left.depth;
        var lrdepth = this.left.right == null ? 0 : this.left.right.depth;

        if (lldepth < lrdepth) {
            // LR Rotation consists of a RR rotation of the left child
            this.left.rotateRR();
            // Plus a LL rotation of this node, which happens anyway
        }
        this.rotateLL();
    } else if (ldepth + 1 < rdepth) {
        // RR or RL rotation
        var rrdepth = this.right.right == null ? 0 : this.right.right.depth;
        var rldepth = this.right.left == null ? 0 : this.right.left.depth;

        if (rldepth > rrdepth) {
            // RR rotation consists of a LL rotation of the right child
            this.right.rotateLL();
            // Plus a RR rotation of this node, which happens anyway
        }
        this.rotateRR();
    }
}

// Insert
AVLTree.prototype.insert = function (value) {
    var childInserted = false;

    if (value == this.value) {
        // Should be all unique
        return false;
    } else if (value < this.value) {
        if (this.left == null) {
            this.left = new AVLTree(value);
            childInserted = true;
        } else {
            childInserted = this.left.insert(value);
            if (childInserted == true) this.balance();
        }
    } else if (value > this.value) {
        if (this.right == null) {
            this.right = new AVLTree(value);
            childInserted = true;
        } else {
            childInserted = this.right.insert(value);
            if (childInserted == true) this.balance();
        }
    }

    if (childInserted == true) this.setDepthBasedOnChildren();
    return childInserted;
}

Time Complexity: $O \lparen nlog_{2} \lparen n \rparen \rparen$
Space Complexity: $O \lparen nlog_{2} \lparen n \rparen \rparen$

Note (📝): Space complexity is from the recursive call stacks in memory.

Deletion (❌🌱❌)

AVL BST is a type of BST, and therefore the deletion function is the same. Adjusting the depths can be done by calling setDepthBasedOnChildren() during traversal:

// AVL Tree
function AVLTree(value) {
    this.left = null;
    this.right = null;
    this.value = value;
    this.depth = 1;
}

// Set Depth Based On Children
AVLTree.prototype.setDepthBasedOnChildren = function () {

    if (this.node == null) {
        this.depth = 0;
    } else {
        this.depth = 1;
    }

    if (this.left != null) {
        this.depth = this.left.depth + 1;
    }

    if (this.right != null && this.depth <= this.right.depth) {
        this.depth = this.right.depth + 1;
    }
}

// Rotate Right
AVLTree.prototype.rotateRR = function () {
    // The right side is too long => rotate from the right
    // (_not_rightwards)
    var valueBefore = this.value;
    var leftBefore = this.left;
    this.value = this.right.value;

    this.left = this.right;
    this.right = this.right.right;
    this.left.right = this.left.left;
    this.left.left = leftBefore;
    this.left.value = valueBefore;

    this.left.updateInNewLocation();
    this.updateInNewLocation();
}

// Rotate Left
AVLTree.prototype.rotateLL = function () {

    var valueBefore = this.value;
    var rightBefore = this.right;
    this.value = this.left.value;

    this.right = this.left;
    this.left = this.left.left;
    this.right.left = this.right.right;
    this.right.right = rightBefore;
    this.right.value = valueBefore;

    this.right.getDepthFromChildren();
    this.getDepthFromChildren();
}

// Balance
AVLTree.prototype.balance = function () {
    var ldepth = this.left == null ? 0 : this.left.depth;
    var rdepth = this.right == null ? 0 : this.right.depth;

    if (ldepth > rdepth + 1) {
        // RR or LL rotation
        var lldepth = this.left.left == null ? 0 : this.left.left.depth;
        var lrdepth = this.left.right == null ? 0 : this.left.right.depth;

        if (lldepth < lrdepth) {
            // LR Rotation consists of a RR rotation of the left child
            this.left.rotateRR();
            // Plus a LL rotation of this node, which happens anyway
        }
        this.rotateLL();
    } else if (ldepth + 1 < rdepth) {
        // RR or RL rotation
        var rrdepth = this.right.right == null ? 0 : this.right.right.depth;
        var rldepth = this.right.left == null ? 0 : this.right.left.depth;

        if (rldepth > rrdepth) {
            // RR rotation consists of a LL rotation of the right child
            this.right.rotateLL();
            // Plus a RR rotation of this node, which happens anyway
        }
        this.rotateRR();
    }
}

// Delete
AVLTree.prototype.remove = function (value) {
    return deleteRecursively(this, value);

    function deleteRecursively(root, value) {
        if (!root) {
            return null;
        } else if (value < root.value) {
            root.left = deleteRecursively(root.left, value);
        } else if (value > root.value) {
            root.right = deleteRecursively(root.right, value);
        } else {
            // No Child
            if (!root.left && !root.right) {
                // Case 1:
                return null;
            } else if (!root.left) {
                root = root.right;
                return root;
            } else if (!root.right) {
                root = root.left;
                return root;
            } else {
                var temp = findMin(root.right);
                root.value = temp.value;
                root.right = deleteRecursively(root.right, temp.value);
                return root;
            }
        }

        // Only difference from the BST one
        root.setDepthBasedOnChildren();
        return root;
    }

    function findMin(root) {
        while (root.left) root = root.left;
        return root;
    }
}

Note (📝):The time complexity and space complexity are both $O \lparen nlog_{2} \lparen n \rparen \rparen$ because AVL trees are balanced. The space complexity is from the recursive call stacks in memory.

Putting It All Together: AVL Tree (🌳🌳🌳)

With the AVL tree class implemented, Figure 15-19 shows an example of an AVL tree produced by the following code block:

// AVL Tree function AVLTree(value) { this.left = null; this.right = null; this.value = value; this.depth = 1; } // Set Depth Based On Children AVLTree.prototype.setDepthBasedOnChildren = function () { if (this.node == null) { this.depth = 1; } if (this.left != null) { this.depth = this.left.depth + 1; } if (this.right != null && this.depth <= this.right.depth) { this.depth = this.right.depth + 1; } } // Rotate Right AVLTree.prototype.rotateRR = function () { // The right side is too long => rotate from the right // (_not_rightwards) var valueBefore = this.value; var leftBefore = this.left; this.value = this.right.value; this.left = this.right; this.right = this.right.right; this.left.right = this.left.left; this.left.left = leftBefore; this.left.value = valueBefore; this.left.setDepthBasedOnChildren(); this.setDepthBasedOnChildren(); } // Rotate Left AVLTree.prototype.rotateLL = function () { var valueBefore = this.value; var rightBefore = this.right; this.value = this.left.value; this.right = this.left; this.left = this.left.left; this.right.left = this.right.right; this.right.right = rightBefore; this.right.value = valueBefore; this.right.setDepthBasedOnChildren(); this.setDepthBasedOnChildren(); } // Balance AVLTree.prototype.balance = function () { var ldepth = this.left == null ? 0 : this.left.depth; var rdepth = this.right == null ? 0 : this.right.depth; if (ldepth > rdepth + 1) { // RR or LL rotation var lldepth = this.left.left == null ? 0 : this.left.left.depth; var lrdepth = this.left.right == null ? 0 : this.left.right.depth; if (lldepth < lrdepth) { // LR Rotation consists of a RR rotation of the left child this.left.rotateRR(); // Plus a LL rotation of this node, which happens anyway } this.rotateLL(); } else if (ldepth + 1 < rdepth) { // RR or RL rotation var rrdepth = this.right.right == null ? 0 : this.right.right.depth; var rldepth = this.right.left == null ? 0 : this.right.left.depth; if (rldepth > rrdepth) { // RR rotation consists of a LL rotation of the right child this.right.rotateLL(); // Plus a RR rotation of this node, which happens anyway } this.rotateRR(); } } // Insert AVLTree.prototype.insert = function (value) { var childInserted = false; if (value == this.value) { // Should be all unique return false; } else if (value < this.value) { if (this.left == null) { this.left = new AVLTree(value); childInserted = true; } else { childInserted = this.left.insert(value); if (childInserted == true) this.balance(); } } else if (value > this.value) { if (this.right == null) { this.right = new AVLTree(value); childInserted = true; } else { childInserted = this.right.insert(value); if (childInserted == true) this.balance(); } } if (childInserted == true) this.setDepthBasedOnChildren(); return childInserted; } // Delete AVLTree.prototype.remove = function (value) { return deleteRecursively(this, value); function deleteRecursively(root, value) { if (!root) { return null; } else if (value < root.value) { root.left = deleteRecursively(root.left, value); } else if (value > root.value) { root.right = deleteRecursively(root.right, value); } else { // No Child if (!root.left && !root.right) { // Case 1: return null; } else if (!root.left) { root = root.right; return root; } else if (!root.right) { root = root.left; return root; } else { var temp = findMin(root.right); root.value = temp.value; root.right = deleteRecursively(root.right, temp.value); return root; } } // Only difference from the BST one root.setDepthBasedOnChildren() return root; } function findMin(root) { while (root.left) root = root.left; return root; } } var avlTest = new AVLTree(1); avlTest.insert(2) avlTest.insert(3) avlTest.insert(4) avlTest.insert(5) avlTest.insert(123) avlTest.insert(203) avlTest.insert(2222) avlTest;

Figure 15-19. AVL result

Note (📝): If a plain binary search tree were used, Figure 15-20 shows what it would look like.

Figure 15-20. BST result

Clearly, this is a skewed binary search tree that is completely unbalanced. At this point, it looks like a linked list. Once the tree becomes completely unbalanced like this, it has a linear time complexity for deletion, insertion, and search instead of logarithmic time.

Summary (📚📚)

Table 15-1 shows the time complexity for binary search tree operation. Compared to other data structures, the search operation is faster than linked lists, arrays, stacks, and queues. As the name implies, a binary search tree is great for searching elements. However, the insertion and deletion operations are slower, with a time complexity of $O \lparen log_{2} \lparen n \rparen \rparen$ instead of $O \lparen 1 \rparen$ like a stack or a queue. Furthermore, all operations become $O \lparen n \rparen$ as the tree becomes unbalanced. To ensure the tree stays balanced, self-balancing trees such as a red-black tree (See on Wikipedia) or an AVL tree should be used.

Operation	Best (If Balanced)	Worst (If Completely Unbalanced)
Deletion	$O \lparen log_{2} \lparen n \rparen \rparen$	$O \lparen n \rparen$
Insertion	$O \lparen log_{2} \lparen n \rparen \rparen$	$O \lparen n \rparen$
Search	$O \lparen log_{2} \lparen n \rparen \rparen$	$O \lparen n \rparen$

Table 15-1.Tree Summary

Challenge (🔥🔥)

These challenge on Trees cover varying problems to aid you solidify the information you have learned from this section. And also, don't forget to post your answer in the comment(with explanation too!): (😃)

---

FIND THE LOWEST COMMON ANCESTOR OF TWO NODES IN A GIVEN BINARY TREE

Problem: The logic for this one is actually fairly simple but hard to notice at first. f the maximum of the two values is smaller than the current root, go left. If the minimum of the two values is bigger than the current root, go right. Figures 15-21 and 15-22 show the two different cases of this:

Figure 15-21. Lowest common ancestor, example 1

Figure 15-22. Lowest common ancestor, example 2

Sample:

function findLowestCommonAncestor(root, value1, value2) { // Code here... } console.log(findLowestCommonAncestor(node1, 0, 2)); // Must print "1" console.log(findLowestCommonAncestor(node2, 0, 2)); // Must print "1" console.log(findLowestCommonAncestor(node1, 0.5, -1)); // Must print "0"

Note (📝): The Time Complexity must be $O \lparen log_{2} \lparen n \rparen \rparen$

---

PRINT NODES NTH DISTANCE FROM THE ROOT

Problem: For this question, traverse the BST in any way (level order was used in this example) and check the height for each BST node to see whether it should be printed.

Sample:

function printKthLevels(root, k) { // Code here... } printKthLevels(node1, 1); // Must print "1" printKthLevels(node1, 2); // Must print "[0,2]"

---

CHECK WHETHER A BINARY TREE IS A SUBTREE OF ANOTHER TREE

Problem: To do this, traverse the binary tree in any way (I’m choosing to do level order) and check whether the one that it is currently on is the same as the subtree:

Sample:

function isSameTree(root1, root2) { // Code here... } function checkIfSubTree(root, subtree) { // Code here... } console.log(checkIfSubTree(node1, node2)); // Must print "true" console.log(checkIfSubTree(node1, node3)); // Must print "false" console.log(checkIfSubTree(node2, node3)); // Must print "false"

---

CHECK WHETHER A TREE IS A MIRROR OF ANOTHER TREE

Problem: Figure 15-23 shows an example.

Figure 15-23. Mirror trees

Here are three possible cases:

• Their root node’s key must be the same.
• The left subtree of root of a and the right subtree root of b are mirrors.
• The right subtree of a and the left subtree of b are mirrors.

Sample:

function isMirrorTrees(tree1, tree2) { // Code here... } console.log(isMirrorTrees(node1, node2)); // Must print "true" console.log(isMirrorTrees(node2, node3)); // Must print "false"

---

Up Next👉 Part 16: Heaps (🔥🔥) (September 5-6, 2020)

---

Learn Data Structure and Algorithm in JavaScript | Part 16

Edison Pebojot(👨‍💻) ・ Sep 6 '20 ・ 29 min read

#javascript #computerscience #beginners #algorithms