README.md

Trees

A brief description of Tree Data Structure in this readme file.

OBJECTIVES

• Define what a tree is
• Compare and contrast trees and lists
• Explain the differences between trees, binary trees, and binary search trees
• Implement operations on binary search trees

WHAT IS A TREE?

A data structure that consists of nodes in a parent / child relationship

👩‍👦

Lists - linear

Trees - nonlinear

TREE TERMINOLOGY

• Root - The top node in a tree.
• Child -A node directly connected to another node when moving away from the Root.
• Parent - The converse notion of a child.
• Siblings -A group of nodes with the same parent.
• Leaf - A node with no children.
• Edge - The connection between one node and another.

KINDS OF TREES

• Simple Trees
• Binary Trees
• Binary Search Trees

SIMPLE TREES

Lots of different applications!

• HTML DOM
• Network Routing
• Abstract Syntax Tree
• Artificial Intelligence
• Folders in Operating Systems
• Computer File Systems

Folders in Operating Systems
HTML DOM
Abstract Syntax Tree

BINARY TREES

Lots of different applications as well!

• Decision Trees (true / false)
• Database Indicies
• Sorting Algorithms

HOW BSTS WORK

• Every parent node has at most two children
• Every node to the left of a parent node is always less than the parent
• Every node to the right of a parent node is always greater than the parent

The BinarySearchTree Class

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
}

INSERTING A NODE

Steps - Iteratively or Recursively

• Create a new node
• Starting at the root
  • Check if there is a root, if not - the root now becomes that new node!
  • If there is a root, check if the value of the new node is greater than or less than the value of the root
  • If it is greater
    • Check to see if there is a node to the right
      • If there is, move to that node and repeat these steps
      • If there is not, add that node as the right property
  • If it is less
    • Check to see if there is a node to the left
      • If there is, move to that node and repeat these steps
      • If there is not, add that node as the left property

INSERTING A NODE SOLUTION

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
}

var tree = new BinarySearchTree();

// tree.insert(10)
// tree.insert(5)
// tree.insert(13)
// tree.insert(11)
// tree.insert(2)
// tree.insert(16)
// tree.insert(7)

Finding a Node in a BST

Steps - Iteratively or Recursively

• Starting at the root
  • Check if there is a root, if not - we're done searching!
  • If there is a root, check if the value of the new node is the value we are looking for. If we found it, we're done!
  • If not, check to see if the value is greater than or less than the value of the root
  • If it is greater
    • Check to see if there is a node to the right
      • If there is, move to that node and repeat these steps
      • If there is not, we're done searching!
  • If it is less
    • Check to see if there is a node to the left
      • If there is, move to that node and repeat these steps
      • If there is not, we're done searching!

Finding a Node in a BST Solution

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
    find(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                found = true;
            }
        }
        if(!found) return undefined;
        return current;
    }
    contains(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                return true;
            }
        }
        return false;
    }
}

var tree = new BinarySearchTree();

// tree.insert(10)
// tree.insert(5)
// tree.insert(13)
// tree.insert(11)
// tree.insert(2)
// tree.insert(16)
// tree.insert(7)

Big O of BST

Insertion - O(log n)

Searching - O(log n)

NOT guaranteed!

THIS IS A VALID BINARY SEARCH TREE

TREE TRAVERSAL

VISIT EVERY NODE ONCE

TRAVERSING A TREE

Two ways:

• Breadth-first Search
• Depth-first Search

BREADTH FIRST SEARCH

Binary Heaps

BFS

Steps - Iteratively

• Create a queue (this can be an array) and a variable to store the values of nodes visited
• Place the root node in the queue
• Loop as long as there is anything in the queue
  • Dequeue a node from the queue and push the value of the node into the variable that stores the nodes
  • If there is a left property on the node dequeued - add it to the queue
  • If there is a right property on the node dequeued - add it to the queue
• Return the variable that stores the values

BFS SOLUTION

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
    find(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                found = true;
            }
        }
        if(!found) return undefined;
        return current;
    }
    contains(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                return true;
            }
        }
        return false;
    }
    BFS(){
        var node = this.root,
            data = [],
            queue = [];
        queue.push(node);

        while(queue.length){
           node = queue.shift();
           data.push(node.value);
           if(node.left) queue.push(node.left);
           if(node.right) queue.push(node.right);
        }
        return data;
    }
}

var tree = new BinarySearchTree();

// tree.insert(10);
// tree.insert(6);
// tree.insert(15);
// tree.insert(3);
// tree.insert(8);
// tree.insert(20);
// tree.BFS();

DEPTH FIRST SEARCH

DFS - PreOrder

Steps - Recursively

• Create a variable to store the values of nodes visited
• Store the root of the BST in a variable called current
• Write a helper function which accepts a node
  • Push the value of the node to the variable that stores the values
  • If the node has a left property, call the helper function with the left property on the node
  • If the node has a right property, call the helper function with the right property on the node
• Invoke the helper function with the current variable
• Return the array of values

DFS - PreOrder Solution

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
    find(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                found = true;
            }
        }
        if(!found) return undefined;
        return current;
    }
    contains(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                return true;
            }
        }
        return false;
    }
    BFS(){
        var node = this.root,
            data = [],
            queue = [];
        queue.push(node);

        while(queue.length){
           node = queue.shift();
           data.push(node.value);
           if(node.left) queue.push(node.left);
           if(node.right) queue.push(node.right);
        }
        return data;
    }
    DFSPreOrder(){
        var data = [];
        function traverse(node){
            data.push(node.value);
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }
}

var tree = new BinarySearchTree();

// tree.insert(10);
// tree.insert(6);
// tree.insert(15);
// tree.insert(3);
// tree.insert(8);
// tree.insert(20);
// tree.DFSPreOrder();

DFS - PostOrder

Steps - Recursively

• Create a variable to store the values of nodes visited
• Store the root of the BST in a variable called current
• Write a helper function which accepts a node
  • If the node has a left property, call the helper function with the left property on the node
  • If the node has a right property, call the helper function with the right property on the node
  • Push the value of the node to the variable that stores the values
  • Invoke the helper function with the current variable
• Return the array of values

DFS - PostOrder Solution

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
    find(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                found = true;
            }
        }
        if(!found) return undefined;
        return current;
    }
    contains(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                return true;
            }
        }
        return false;
    }
    BFS(){
        var node = this.root,
            data = [],
            queue = [];
        queue.push(node);

        while(queue.length){
           node = queue.shift();
           data.push(node.value);
           if(node.left) queue.push(node.left);
           if(node.right) queue.push(node.right);
        }
        return data;
    }
    DFSPreOrder(){
        var data = [];
        function traverse(node){
            data.push(node.value);
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }
    DFSPostOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
            data.push(node.value);
        }
        traverse(this.root);
        return data;
    }
}


var tree = new BinarySearchTree();

// tree.insert(10);
// tree.insert(6);
// tree.insert(15);
// tree.insert(3);
// tree.insert(8);
// tree.insert(20);
// tree.DFSPostOrder();

DFS - InOrder

Steps - Recursively

• Create a variable to store the values of nodes visited
• Store the root of the BST in a variable called current
• Write a helper function which accepts a node
  • If the node has a left property, call the helper function with the left property on the node
  • Push the value of the node to the variable that stores the values
  • If the node has a right property, call the helper function with the right property on the node
• Invoke the helper function with the current variable
• Return the array of values

DFS - InOrder Solution

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
    find(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                found = true;
            }
        }
        if(!found) return undefined;
        return current;
    }
    contains(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                return true;
            }
        }
        return false;
    }
    BFS(){
        var node = this.root,
            data = [],
            queue = [];
        queue.push(node);

        while(queue.length){
           node = queue.shift();
           data.push(node.value);
           if(node.left) queue.push(node.left);
           if(node.right) queue.push(node.right);
        }
        return data;
    }
    DFSPreOrder(){
        var data = [];
        function traverse(node){
            data.push(node.value);
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }
    DFSPostOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
            data.push(node.value);
        }
        traverse(this.root);
        return data;
    }
    DFSInOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            data.push(node.value);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }
}

var tree = new BinarySearchTree();

// tree.insert(10);
// tree.insert(6);
// tree.insert(15);
// tree.insert(3);
// tree.insert(8);
// tree.insert(20);
// tree.DFSInOrder();

BFS? DFS?

Which is better? 🤔

RECAP

• Trees are non-linear data structures that contain a root and child nodes
• Binary Trees can have values of any type, but at most two children for each parent
• Binary Search Trees are a more specific version of binary trees where every node to the left of a parent is less than it's value and every node to the right is greater
• We can search through Trees using BFS and DFS