12. Trees - marinakosova/master-the-coding-interview GitHub Wiki
Trees
Trees are wonderful data structures that can model real life hierarchical information, including organizational charts, genealogical trees, computer file systems, HTML elements on a web page (also known as the Document Object Model, or DOM), state diagrams, and more.
A tree is composed of tree nodes. A tree node is a very simple data structure that contains:
- Data
- A list of children, where each child is itself a tree node
We can add data to and remove data from a tree and traverse it in two different ways:
- Depth-first, or
- Breadth-first
Depth-first Tree Traversal
15
-- 3
-- -- 6
-- -- 9
-- 12
-- -- 19
-- -- 8
-- 0
-- -- 10
-- -- 19
we can traverse it depth-wise to produce this result:
15
3
6
9
12
19
8
0
10
19
Breadth-first Tree Traversal
15
-- 3
-- -- 6
-- -- 9
-- 12
-- -- 19
-- -- 8
-- 0
-- -- 10
-- -- 19
we can traverse it breadth-wise to produce this result:
15
3
12
0
6
9
19
8
10
19
Tree Implementation (from Codecademy)
class TreeNode {
constructor(data) {
this.data = data;
this.children = [];
}
addChild(child) {
if (child instanceof TreeNode) {
this.children.push(child);
} else {
this.children.push(new TreeNode(child));
}
}
removeChild(childToRemove) {
const length = this.children.length;
this.children = this.children.filter(child => {
return childToRemove instanceof TreeNode
? child !== childToRemove
: child.data !== childToRemove;
});
if (length === this.children.length) {
this.children.forEach(child => child.removeChild(childToRemove));
}
}
print(level = 0) {
let result = '';
for (let i = 0; i < level; i++) {
result += '-- ';
}
console.log(`${result}${this.data}`);
this.children.forEach(child => child.print(level + 1));
}
depthFirstTraversal() {
console.log(this.data);
this.children.forEach(child => child.depthFirstTraversal());
}
breadthFirstTraversal() {
let queue = [this];
while(queue.length > 0) {
const current = queue.shift();
console.log(current.data);
queue = queue.concat(current.children);
}
}
};
const TreeNode = require('./TreeNode');
const tree = new TreeNode(15);
const randomize = () => Math.floor(Math.random() * 20);
// add first-level children
for (let i = 0; i < 3; i++) {
tree.addChild(randomize());
}
// add second-level children
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 2; j++) {
tree.children[i].addChild(randomize());
}
}
tree.print();
tree.breadthFirstTraversal();
Binary Search Tree
Constraints are placed on the data or node arrangement of a tree to solve difficult problems like efficient search.
A binary tree is a type of tree where each parent can have no more than two children, known as the left child and right child.
Further constraints make a binary search tree:
- Left child values must be lesser than their parent.
- Right child values must be greater than their parent.
- The constraints of a binary search tree allow us to search the tree efficiently. At each node, we can discard half of the remaining possible values!
BST (from Udemy)
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;
}
Balance the Tree: AVL Trees + Red Black Trees
Animation of AVL Trees
How it works
Animation of Red Black Trees
How it works
You can compare the technical details between the two here.