aTrees 1. Introduction 2. Binary Trees 3. O(log N) 4. Binary Search Tree 4.1. Balanced vs. Unbalanced BST 4.2. Pros and Cons of BST 4.3. BST Implementation 5. AVL and Red Black Trees 6. Binary Heaps 7. Priority Queue 8. Trie

1. Introduction• Trees have hierarchical structure as opposed to something like linked lists or arrays.• Trees are not (necessarily) linear. As opposed to arrays (or linked lists) that are linear, trees can have zero or more child nodes.• A tree starts with a root (parent) node and every child of the tree descends from this root node.• Leaf nodes are the nodes at the very end of the data structure.• Examples of tree data structure application:– The DOM (Document Object Model).– Comments on Facebook– Abstract Syntax Tree– 2. Binary Trees• A binary tree is a type of tree with a few rules:– Each node can only have either zero, one or two child nodes.– Each child can only have one parent.• A Perfect Binary Tree is a binary tree where each parent have two childs.– When binary trees are perfect, they have two really interesting properties:* The number of total nodes on each level doubles we move down the tree.* The number of nodes on the last level is equal to the sum of the number of nodes on all the other levels plus 1. This means about (due to plus 1) of our nodes are one the last level, which means half of our data is on the last level.· This is an interesting property. If somehow we can avoid visiting every node, even if the node we're looking for is at the bottom, perhaps there's some efficiencies that we can have.– The number of nodes are each level h${\displaystyle h}$ is equal to 2h${\displaystyle 2^h}$, where h${\displaystyle h}$ is the tree level.– Total number of nodes is 2n-1${\displaystyle 2^n-1}$ where n${\displaystyle n}$ is number of levels in a tree.• A Full Binary Tree is a binary tree where each parent either 0 or 2 childs (no 1-child parent). 3. O(log N)• Consider a perfect binary tree. We can say log(nodes) = level${\displaystyle \log (nodes)=level}$, i.e. log22h = h${\displaystyle lo{g}_2{2}^h=h}$. • O(logN)${\displaystyle O(\log N)}$ simply means that based on the height, the maximum number of decisions that we're going to take is log(n)${\displaystyle log(n)}$. – In other words, O(logN)${\displaystyle O(\log N)}$ means that the choice of the next element is one of several possibilities and only one needs to be chosen.– An example of that checking a name on a phone book. You don't actually check every name on the book. You start looking by where their name is alphabetically (divide and conquer).– 4. Binary Search Tree• Binary Search Tree (BST) is the most common tree data structure.• Rule of BST:– All child nodes in the tree to the right of root node must be greater than the current node, i.e. if keep going to the right of each node, the value constantly increases. In other words, when you go to the right the value always increases.* This automatically means that if you go to the left, the value decreases.– A node can only have up to two children.• BSTs are great searching and comparing things.• It has the advantage over hash tables as BST also preserves relationships. • The Big-O operations for BST is,

Lookup	O(logN)${\displaystyle O(\log N)}$
Insert	O(logN)${\displaystyle O(\log N)}$
Delete	O(logN)${\displaystyle O(\log N)}$

Table 1:Big-O of Binary Search Tree

• Insert and delete are O(logN)${\displaystyle O(\log N)}$ because we still need to get to index of insertion/deletion.• The lookup is O(logN)${\displaystyle O(\log N)}$ because search space gets exponentially smaller as we traverse down the tree. We don't need to traverse every single n${\displaystyle n}$ nodes.4.1. Balanced vs. Unbalanced BST• Unbalanced BST happens when one side of the tree (right or left) becomes much larger than the other side.• Why unbalanced BST is bad?– Because the tree starts looking like a long linked list, hence, the operations (mentioned above) will approximating to O(n)${\displaystyle O(n)}$.• Ideally, we want a balanced BST. How can we balance a BST?– There are algorithms to do that. AVL Tree, Red Black Tree. We will discuss this more later.– Note: In interview question, they won't ask you to balance a BST.4.2. Pros and Cons of BST• Most operations in a BST are better than O(n)${\displaystyle O(n)}$. • It's also ordered.• Also, because we can place the node anywhere in the memory, we can have flexible size.• The downside is that it has no O(1)${\displaystyle O(1)}$ operation.• BSTs perform really well as long as you make sure that you stay away from the edge cases and also balance the tree. 4.3. BST Implementation• Here is an implementation of BST in JS:

class Node { constructor(value){ this.left = null; this.right = null; this.value = value; }} class BinarySearchTree { constructor(){ this.root = null; } insert(value){ const newNode = new Node(value); if (this.root === null) { this.root = newNode; } else { let currentNode = this.root; while(true){ if(value < currentNode.value){ //Left if(!currentNode.left){ currentNode.left = newNode; return this; } currentNode = currentNode.left; } else { //Right if(!currentNode.right){ currentNode.right = newNode; return this; } currentNode = currentNode.right; } } } } lookup(value){ if (!this.root) { return false; } let currentNode = this.root; while(currentNode){ if(value < currentNode.value){ currentNode = currentNode.left; } else if(value > currentNode.value){ currentNode = currentNode.right; } else if (currentNode.value === value) { return currentNode; } } return null } remove(value) { if (!this.root) { return false; } let currentNode = this.root; let parentNode = null; while(currentNode){ if(value < currentNode.value){ parentNode = currentNode; currentNode = currentNode.left; } else if(value > currentNode.value){ parentNode = currentNode; currentNode = currentNode.right; } else if (currentNode.value === value) { //We have a match, get to work! //Option 1: No right child: if (currentNode.right === null) { if (parentNode === null) { this.root = currentNode.left; } else { //if parent > current value, make current left child a child of parent if(currentNode.value < parentNode.value) { parentNode.left = currentNode.left; //if parent < current value, make left child a right child of parent } else if(currentNode.value > parentNode.value) { parentNode.right = currentNode.left; } } //Option 2: Right child which doesnt have a left child } else if (currentNode.right.left === null) { currentNode.right.left = currentNode.left; if(parentNode === null) { this.root = currentNode.right; } else { //if parent > current, make right child of the left the parent if(currentNode.value < parentNode.value) { parentNode.left = currentNode.right; //if parent < current, make right child a right child of the parent } else if (currentNode.value > parentNode.value) { parentNode.right = currentNode.right; } } //Option 3: Right child that has a left child } else { //find the Right child's left most child let leftmost = currentNode.right.left; let leftmostParent = currentNode.right; while(leftmost.left !== null) { leftmostParent = leftmost; leftmost = leftmost.left; } //Parent's left subtree is now leftmost's right subtree leftmostParent.left = leftmost.right; leftmost.left = currentNode.left; leftmost.right = currentNode.right; if(parentNode === null) { this.root = leftmost; } else { if(currentNode.value < parentNode.value) { parentNode.left = leftmost; } else if(currentNode.value > parentNode.value) { parentNode.right = leftmost; } } } return true; } } }} const tree = new BinarySearchTree();tree.insert(9)tree.insert(4)tree.insert(6)tree.insert(20)tree.insert(170)tree.insert(15)tree.insert(1)tree.remove(170)JSON.stringify(traverse(tree.root)) // 9// 4 20//1 6 15 170 function traverse(node) { const tree = { value: node.value }; tree.left = node.left === null ? null : traverse(node.left); tree.right = node.right === null ? null : traverse(node.right); return tree;}

5. AVL and Red Black Trees• Ideally, you want to have a balanced BST.• Although we built our own tree in the previous section, but in production we're going to use either of AVL or Red Black trees that automatically rebalance.• Some resources to learn more about these trees:– How AVL Tree works?, Animation– How Red Black Tree works?, Animation– Technical comparison between the two6. Binary Heaps• In binary heap every child belongs to a parent node that has a greater priority or value.– Max Heap: Every child has a lower value than its parent.– Min Heap: Every child has a higher value than its parent.• Binary heaps do left to right insertion, so they won't get unbalanced.• Binary heaps are memory efficient because it's always a complete binary tree.• Heap can be used in any algorithm where ordering is important.– It's commonly used when it comes to priority queues.• Binary heaps are used in cases where you want to find the min or the max.• Binary heaps are really great at doing comparative operations.– Example: I want all the nodes above a certain value. This is a O(n)${\displaystyle O(n)}$ in BST.• Heaps are used a lot in data storage, priority queues and sorting algorithms.• Note: Memory Heaps are NOT the same as heap data structure. Memory heaps are free storage where you can store arbitrarily.

Lookup	O(n)${\displaystyle O(n)}$
Insert	O(logN)${\displaystyle O(\log N)}$
Delete	O(logN)${\displaystyle O(\log N)}$

Table 2:Big-O of Binary Heap

7. Priority Queue• In priority queue, each element has a priority and they're operated based on their priority.– Example: Emergency room in hospitals, VIP enterance in night clubs, airplane boarding, etc.• Priority queue implementation in JS 8. Trie• A trie is a specialized tree used in searching, most often with text.• In most cases, it can outperform BST, hash tables and most other data structures.• Trie allows you to know if a word (or part of word) exists in a body of text.• Trie usually has an empty root node (the start node).• Another name for it is prefix tree.• It's like auto-completion (like in Google Search).• Applications: searching a word in dictionary, providing auto suggestion, IP routing, etc.• The Big-O of trie is O(length of the word)${\displaystyle O(lengthoftheword)}$.• Trie also has a major advantage when it comes to space complexity since we use prefixes of different words so we don't have to use the same letter multiple times.