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
"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, welldefined root."
#JavaScript #100DaysOfCode15:55 PM  25 Aug 2020
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
Prerequisite (✋😐)
If you're reading this article right now, please considered to read our Part 01: BigO Notation, Part 02: JavaScript Unique Part, Part 03: JavaScript Numbers to Part 14: Caching

Part Table of Contents Description 01 BigO 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 BigO is important for analyzing and comparing the efficiencies of algorithms. The analysis of BigO starts by looking at the code, and, applying the rules, applying the rules is because to simplify the BigO 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 builtin functions. You will learn how to access, compare, decompose, and search strings for commonly used reallife 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 builtin 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 fixedsized 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 rereading the hard drive, and a web browser caches web images to avoid redownloading. 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 selfbalancing 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 selfbalancing 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. (👍)
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 selfbalancing 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 selfbalancing 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 151 can have any number of children.

Figure 151. Generalized tree with any number of children
The code block for the node in the Figure 151 (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 152. Binary tree
See the following code and Figure 152 (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: preorder traversal, postorder traversal, inorder traversal, and levelorder traversal.
PreOrder Traversal (➡️📦❌)
Preorder traversal visits nodes in the following order: (1️⃣) root, (2️⃣) left, and (3️⃣) right. In Figure 153, 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 153:

Figure 153. Preorder 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;
}
// PreOrder 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;
}
// PreOrder 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]$
InOrder Traversal (📦➡️❌)
Inorder traversal visits nodes in the following order: (1️⃣) left, (2️⃣) root (current node), (3️⃣) right

Figure 154. Inorder traversal
Inorder 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;
}
// InOrder 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;
}
// InOrder 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 ]$
PostOrder Traversal (❌📦➡️)
Postorder traversal visits nodes in the following order: (1️⃣) left, (2️⃣) right, (3️⃣) root. For the tree shown in Figure 155, the gray squares indicate the inorder traversal. As you can see, 10 is printed first, and 42 is printed last:

Figure 155. Postorder traversal
Here’s the code:
// Binary Tree
function BinaryTree() {
this._root = null;
}
// PostOrder 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;
}
// PostOrder 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 ]$
LevelOrder Traversal (➡️📏❌)
Levelorder traversal is also known as breadth first search (BFS):

Figure 156. Levelorder 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;
}
// LevelOrder 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 preorder
traversal because you will encounter all the roots before all the leaves (🍃). If you need to explore all the leaves before any nodes, choose postorder 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 inorder traversal. The tree would be flattened in the same way it was created. A preorder or postorder 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 157 (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 157. 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 157 (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 158 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 158. 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:
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 selfbalancing 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 AdelsonVelsky (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 159 (below). The 45 becomes the parent node in Figure 1510 (below) to balance the BST:

Figure 159. Rotate left before

Figure 1510. 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 1511. The 55 node becomes the parent in Figure 1512 to balance the BST:
 Figure 1511. Rotate right before

Figure 1512. 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 1513 (below) shows a BST where the height is $3$ . By rotating right and then left, as shown in Figure 1514 (below) and Figure 1515 (below), balance is achieved:

Figure 1513. A situation where rotating right and then rotating left is appropriate

Figure 1514. Rotate right first

Figure 1515. Rotate left after
Rotate Left And Then Right (2️⃣↩️2️⃣↪️)
Similarly, Figure 1516 shows a BST where the height is $3$ . By rotating left and then right, as shown in Figure 1517 and Figure 1518, balance is achieved:

Figure 1516. A situation where rotating left and then rotating right is appropriate

Figure 1517. Rotate left first

Figure 1518. 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 1519 shows an example of an AVL tree produced by the following code block:

Figure 1519. AVL result
Note (📝): If a plain binary search tree were used, Figure 1520 shows what it would look like.

Figure 1520. 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 151 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, selfbalancing trees such as a redblack 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 151.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 1521 and 1522 show the two different cases of this:

Figure 1521. Lowest common ancestor, example 1

Figure 1522. Lowest common ancestor, example 2
Sample:
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:
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:
CHECK WHETHER A TREE IS A MIRROR OF ANOTHER TREE
Problem: Figure 1523 shows an example.

Figure 1523. 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:
Up Next👉 Part 16: Heaps (🔥🔥) (September 56, 2020)
Article No Longer Available
Posted on by:
Discussion