AlgoDaily - An Executable Data Structures Cheat Sheet for Interviews

Introduction/Arrays

const arr = [1, 2, 3];

arr = [1, 2, 3]

int[] arr = {1, 2, 3};

int arr[] = {1, 2, 3};

int[] arr = {1, 2, 3};

arr := []int{1, 2, 3}

```js
// instantiation
let empty = new Array();
let teams = new Array('Knicks', 'Mets', 'Giants');

// literal notation
let otherTeams = ['Nets', 'Patriots', 'Jets'];

// size
console.log('Size:', otherTeams.length);

// access
console.log('Access:', teams[0]);

// sort
const sorted = teams.sort();
console.log('Sorted:', sorted);

// search
const filtered = teams.filter((team) => team === 'Knicks');
console.log('Searched:', filtered);

```
```py
# Python does not have a native support for arrays, but has a List data structure
# which mimicks the behavior of an array. The Python array module requires all
# array elements to be of the same type. We implement our own below.

class Array(object):
    """
    sizeOfArray: denotes the total size of the array to be initialized
    arrayType: denotes the data type of the array
    arrayItems: values at each position of array
    """

    def __init__(self, sizeOfArray, arrayType=int):
        self.sizeOfArray = len(list(map(arrayType, range(sizeOfArray))))
        self.arrayItems = [arrayType(0)] * sizeOfArray  # initialize array with zeroes

    def __str__(self):
        return " ".join([str(i) for i in self.arrayItems])

    # function for search
    def search(self, keyToSearch):
        for i in range(self.sizeOfArray):
            if self.arrayItems[i] == keyToSearch:  # brute-forcing
                return i  # index at which element/key was found

        return -1  # if key not found, return -1

    # function for inserting an element
    def insert(self, keyToInsert, position):
        if self.sizeOfArray > position:
            for i in range(self.sizeOfArray - 2, position - 1, -1):
                self.arrayItems[i + 1] = self.arrayItems[i]
            self.arrayItems[position] = keyToInsert
        else:
            print("Array size is:", self.sizeOfArray)

    # function to delete an element
    def delete(self, keyToDelete, position):
        if self.sizeOfArray > position:
            for i in range(position, self.sizeOfArray - 1):
                self.arrayItems[i] = self.arrayItems[i + 1]
        else:
            print("Array size is:", self.sizeOfArray)


a = Array(10, int)
a.insert(0, 1)
a.insert(1, 2)
a.insert(2, 3)
print(a)
```
```java
public class Main {
    public static void main(String[] args) {
        // Compiles and runs fine
        int[] array = new int[0];

        try {
            // Throws java.lang.ArrayIndexOutOfBoundsException
            array[0] = 1;
        } catch (Exception e) {
            System.out.println(e);
        }

        try {
            // Throws java.lang.NegativeArraySizeException
            int[] arr = new int[-1];
        } catch (Exception e) {
            System.out.println(e);
        }

        String[] suit = {
            "spades",
            "hearts",
            "diamonds",
            "clubs"
        };

        // Should print 4 in this case
        System.out.println(suit.length);
    }
}
```
```cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // instantiation
    std::vector<std::string> empty;
    std::vector<std::string> teams{"Knicks", "Mets", "Giants"};

    // literal notation (similar to instantiation)
    std::vector<std::string> otherTeams{"Nets", "Patriots", "Jets"};

    // size
    std::cout << "Size: " << otherTeams.size() << std::endl;

    // access
    std::cout << "Access: " << teams[0] << std::endl;

    // sort
    std::sort(teams.begin(), teams.end());
    std::cout << "Sorted:";
    for (const auto &team : teams) {
        std::cout << " " << team;
    }
    std::cout << std::endl;

    // search
    auto it = std::find(teams.begin(), teams.end(), "Knicks");
    std::cout << "Searched: " << (it != teams.end() ? *it : "Not Found") << std::endl;

    return 0;
}
```
```csharp
using System;
using System.Collections.Generic;

public class MainClass
{
    public static void Main(string[] args)
    {
        // instantiation
        List<string> empty = new List<string>();
        List<string> teams = new List<string>{"Knicks", "Mets", "Giants"};

        // literal notation (similar to instantiation)
        List<string> otherTeams = new List<string>{"Nets", "Patriots", "Jets"};

        // size
        Console.WriteLine("Size: " + otherTeams.Count);

        // access
        Console.WriteLine("Access: " + teams[0]);

        // sort
        teams.Sort();
        Console.WriteLine("Sorted: " + string.Join(", ", teams));

        // search
        bool containsKnicks = teams.Contains("Knicks");
        Console.WriteLine("Searched: " + (containsKnicks ? "Knicks" : "Not Found"));
    }
}
```
```go
package main

import (
	"fmt"
	"sort"
)

func main() {
	// instantiation
	var empty []string
	teams := []string{"Knicks", "Mets", "Giants"}

	// literal notation
	otherTeams := []string{"Nets", "Patriots", "Jets"}

	// size
	fmt.Println("Size:", len(otherTeams))

	// access
	fmt.Println("Access:", teams[0])

	// sort
	sort.Strings(teams)
	fmt.Println("Sorted:", teams)

	// search
	found := false
	for _, team := range teams {
		if team == "Knicks" {
			fmt.Println("Searched: Knicks")
			found = true
			break
		}
	}
	if !found {
		fmt.Println("Searched: Not Found")
	}
}
```

Dynamic Array

```js
/* Arrays are dynamic in Javascript :-) */

// instantiation
let empty = new Array();
let teams = new Array('Knicks', 'Mets', 'Giants');

// literal notation
let otherTeams = ['Nets', 'Patriots', 'Jets'];

// size
console.log('Size:', otherTeams.length);

// access
console.log('Access:', teams[0]);

// sort
const sorted = teams.sort();
console.log('Sorted:', sorted);

// search
const filtered = teams.filter((team) => team === 'Knicks');
console.log('Searched:', filtered);

```
```py
# Python does not have a native support for arrays, but has a List data structure
# which mimicks the behavior of an array. The Python array module requires all
# array elements to be of the same type. We implement our own below.

class Array(object):
    """
    sizeOfArray: denotes the total size of the array to be initialized
    arrayType: denotes the data type of the array
    arrayItems: values at each position of array
    """

    def __init__(self, sizeOfArray, arrayType=int):
        self.sizeOfArray = len(list(map(arrayType, range(sizeOfArray))))
        self.arrayItems = [arrayType(0)] * sizeOfArray  # initialize array with zeroes

    def __str__(self):
        return " ".join([str(i) for i in self.arrayItems])

    # function for search
    def search(self, keyToSearch):
        for i in range(self.sizeOfArray):
            if self.arrayItems[i] == keyToSearch:  # brute-forcing
                return i  # index at which element/key was found

        return -1  # if key not found, return -1

    # function for inserting an element
    def insert(self, keyToInsert, position):
        if self.sizeOfArray > position:
            for i in range(self.sizeOfArray - 2, position - 1, -1):
                self.arrayItems[i + 1] = self.arrayItems[i]
            self.arrayItems[position] = keyToInsert
        else:
            print("Array size is:", self.sizeOfArray)

    # function to delete an element
    def delete(self, keyToDelete, position):
        if self.sizeOfArray > position:
            for i in range(position, self.sizeOfArray - 1):
                self.arrayItems[i] = self.arrayItems[i + 1]
        else:
            print("Array size is:", self.sizeOfArray)


a = Array(10, int)
a.insert(0, 1)
a.insert(1, 2)
a.insert(2, 3)
print(a)
```
```java
// Java has the ArrayList data structure that provides dynamic array functionality.
// It's utilized in the below example.

import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {
        ArrayList < Integer > myNumbers = new ArrayList < Integer > ();
        myNumbers.add(10);
        myNumbers.add(15);
        myNumbers.add(20);
        myNumbers.add(25);
        for (int i: myNumbers) {
            System.out.println(i);
        }

    }
}
```
```cpp
// C++ provides the vector data structure for dynamic arrays

#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers; // Declaration
    numbers.push_back(10);
    numbers.push_back(15);
    numbers.push_back(20);
    numbers.push_back(25);
    
    // Iterating through the vector and printing the numbers
    for (int number : numbers) {
        std::cout << number << std::endl;
    }

    return 0;
}
```
```csharp
// C# has the List data structure which functions like a dynamic array

using System;
using System.Collections.Generic;

class Program {
    static void Main(string[] args) {
        List<int> numbers = new List<int>();
        numbers.Add(10);
        numbers.Add(15);
        numbers.Add(20);
        numbers.Add(25);
        
        foreach (int number in numbers) {
            Console.WriteLine(number);
        }
    }
}
```
```go
// Go has slices which provide the functionality of a dynamic array

package main

import "fmt"

func main() {
	var numbers []int // Declaration
	numbers = append(numbers, 10)
	numbers = append(numbers, 15)
	numbers = append(numbers, 20)
	numbers = append(numbers, 25)

	for _, number := range numbers {
		fmt.Println(number)
	}
}
```

Size vs Capacity

Dynamic Array Resize Trace

Linked List

```js
function LinkedListNode(val) {
  this.val = val;
  this.next = null;
}

class MyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  prepend(newVal) {
    const currentHead = this.head;
    const newNode = new LinkedListNode(newVal);
    newNode.next = currentHead;
    this.head = newNode;

    if (!this.tail) {
      this.tail = newNode;
    }
  }

  append(newVal) {
    const newNode = new LinkedListNode(newVal);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
}

var linkedList1 = new MyLinkedList();
linkedList1.prepend(25);
linkedList1.prepend(15);
linkedList1.prepend(5);
linkedList1.prepend(9); 
console.log(linkedList1);

```
```py
class LinkedListNode:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next_node = next_node

    def set_next(self, next_node):
        self.next_node = next_node

    def get_next(self):
        return self.next_node

    def get_value(self):
        return self.value


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def prepend(self, value):
        new_node = LinkedListNode(value)
        new_node.set_next(self.head)
        self.head = new_node

        if self.tail is None:
            self.tail = new_node

    def append(self, value):
        new_node = LinkedListNode(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.set_next(new_node)
            self.tail = new_node

    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.get_value(), end=" ")
            current_node = current_node.get_next()
        print()


if __name__ == "__main__":
    linked_list = LinkedList()
    linked_list.prepend(25)
    linked_list.prepend(15)
    linked_list.prepend(5)
    linked_list.prepend(9)
    linked_list.print_list()

```
```java
class Node {
    private int value;
    private Node next;

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }

    public int getVal() {
        return value;
    }

    public void setVal(int value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }


}

class LinkedList {
    private Node head;

    public LinkedList() {
        this.head = null;
    }

    public void insert(int val, Node next) {
        Node newNode = new Node(val, next);

        if (this.head == null) {
            this.head = newNode;
        } else {
            Node current = this.head;
            while (current.getNext() != null) {
                current = current.getNext();
            }

            current.setNext(newNode);
        }
    }

    public Node getLastNode() {
        Node current = this.head;

        if (current == null) {
            return null;
        }

        while (current.getNext() != null) {
            current = current.getNext();
        }

        return current;
    }

    public Node find(int val) {
        Node current = this.head;

        if (current == null) {
            return null;
        }

        while (current.getNext() != null) {
            if (current.getVal() == val) {
                return current;
            }
            current = current.getNext();
        }

        return null;
    }

    public void print() {
        Node current = this.head;

        while (current != null) {
            System.out.print(current.getVal() + " ");
            current = current.getNext();
        }
    }

    public int length() {
        int count = 0;
        Node current = this.head;

        while (current != null) {
            count++;
            current = current.getNext();
        }

        return count;
    }

    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }


}

public class Main {

    public static void main(String[] args) {
        LinkedList ll = new LinkedList();
        LinkedList list = new LinkedList();

        list.insert(1, null);
        list.insert(2, null);
        list.insert(3, null);
        list.insert(4, null);
        list.insert(5, null);
        list.print();
    }
}
```
```cpp
#include <iostream>

class Node {
    int value;
    Node* next;

public:
    Node(int value, Node* next = nullptr) : value(value), next(next) {}

    int getVal() {
        return value;
    }

    void setVal(int value) {
        this->value = value;
    }

    Node* getNext() {
        return next;
    }

    void setNext(Node* next) {
        this->next = next;
    }
};

class LinkedList {
    Node* head;

public:
    LinkedList() : head(nullptr) {}

    void insert(int val, Node* next = nullptr) {
        Node* newNode = new Node(val, next);

        if (this->head == nullptr) {
            this->head = newNode;
        } else {
            Node* current = this->head;
            while (current->getNext() != nullptr) {
                current = current->getNext();
            }

            current->setNext(newNode);
        }
    }

    Node* getLastNode() {
        Node* current = this->head;

        if (current == nullptr) {
            return nullptr;
        }

        while (current->getNext() != nullptr) {
            current = current->getNext();
        }

        return current;
    }

    Node* find(int val) {
        Node* current = this->head;

        if (current == nullptr) {
            return nullptr;
        }

        while (current->getNext() != nullptr) {
            if (current->getVal() == val) {
                return current;
            }
            current = current->getNext();
        }

        return nullptr;
    }

    void print() {
        Node* current = this->head;

        while (current != nullptr) {
            std::cout << current->getVal() << " ";
            current = current->getNext();
        }
    }

    int length() {
        int count = 0;
        Node* current = this->head;

        while (current != nullptr) {
            count++;
            current = current->getNext();
        }

        return count;
    }

    Node* getHead() {
        return head;
    }

    void setHead(Node* head) {
        this->head = head;
    }
};

int main() {
    LinkedList ll;
    LinkedList list;

    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.insert(4);
    list.insert(5);
    list.print();
}
```
```csharp
class Node {
    public int Value { get; set; }
    public Node Next { get; set; }

    public Node(int value, Node next = null) {
        Value = value;
        Next = next;
    }
}

class LinkedList {
    public Node Head { get; set; }

    public LinkedList() {
        Head = null;
    }

    public void Insert(int val, Node next = null) {
        Node newNode = new Node(val, next);

        if (Head == null) {
            Head = newNode;
        } else {
            Node current = Head;
            while (current.Next != null) {
                current = current.Next;
            }

            current.Next = newNode;
        }
    }

    public Node GetLastNode() {
        Node current = Head;

        if (current == null) {
            return null;
        }

        while (current.Next != null) {
            current = current.Next;
        }

        return current;
    }

    public Node Find(int val) {
        Node current = Head;

        if (current == null) {
            return null;
        }

        while (current.Next != null) {
            if (current.Value == val) {
                return current;
            }
            current = current.Next;
        }

        return null;
    }

    public void Print() {
        Node current = Head;

        while (current != null) {
            Console.Write(current.Value + " ");
            current = current.Next;
        }
    }

    public int Length() {
        int count = 0;
        Node current = Head;

        while (current != null) {
            count++;
            current = current.Next;
        }

        return count;
    }
}

public class Program {
    public static void Main(string[] args) {
        LinkedList list = new LinkedList();
        list.Insert(1);
        list.Insert(2);
        list.Insert(3);
        list.Insert(4);
        list.Insert(5);
        list.Print();
    }
}
```
```go
type Node struct {
    Value int
    Next  *Node
}

type LinkedList struct {
    Head *Node
}

func (list *LinkedList) Insert(val int, next *Node) {
    newNode := &Node{val, next}

    if list.Head == nil {
        list.Head = newNode
    } else {
        current := list.Head
        for current.Next != nil {
            current = current.Next
        }

        current.Next = newNode
    }
}

func (list *LinkedList) GetLastNode() *Node {
    current := list.Head

    if current == nil {
        return nil
    }

    for current.Next != nil {
        current = current.Next
    }

    return current
}

func (list *LinkedList) Find(val int) *Node {
    current := list.Head

    if current == nil {
        return nil
    }

    for current.Next != nil {
        if current.Value == val {
            return current
        }
        current = current.Next
    }

    return nil
}

func (list *LinkedList) Print() {
    current := list.Head

    for current != nil {
        fmt.Print(current.Value, " ")
        current = current.Next
    }
}

func (list *LinkedList) Length() int {
    count := 0
    current := list.Head

    for current != nil {
        count++
        current = current.Next
    }

    return count
}

func main() {
    list := &LinkedList{}
    list.Insert(1, nil)
    list.Insert(2, nil)
    list.Insert(3, nil)
    list.Insert(4, nil)
    list.Insert(5, nil)
    list.Print()
}
```

Pointer Tradeoff

Queue

```js
class Queue {
  constructor() {
    this.queue = [];
  }

  enqueue(item) {
    return this.queue.unshift(item);
  }

  dequeue() {
    return this.queue.pop();
  }

  peek() {
    return this.queue[this.length - 1];
  }

  get length() {
    return this.queue.length;
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue);

queue.dequeue();
console.log(queue);

```
```py
class Queue(object):
    def __init__(self, limit = 10):
        self.queue = []
        self.front = None
        self.rear = None
        self.limit = limit
        self.size = 0

    def __str__(self):
        return ' '.join([str(i) for i in self.queue])

    # to check if queue is empty
    def isEmpty(self):
        return self.size <= 0

    # to add an element from the rear end of the queue
    def enqueue(self, data):
        if self.size >= self.limit:
            return -1          # queue overflow
        else:
            self.queue.append(data)

        # assign the rear as size of the queue and front as 0
        if self.front is None:
            self.front = self.rear = 0
        else:
            self.rear = self.size

        self.size += 1

    # to pop an element from the front end of the queue
    def dequeue(self):
        if self.isEmpty():
            return -1          # queue underflow
        else:
            self.queue.pop(0)
            self.size -= 1
            if self.size == 0:
                self.front = self.rear = 0
            else:
                self.rear = self.size - 1

    def getSize(self):
        return self.size

if __name__ == '__main__':
    myQueue = Queue()
    for i in range(10):
        myQueue.enqueue(i)
    print(myQueue)
    print('Queue Size:',myQueue.getSize())
    myQueue.dequeue()
    print(myQueue)
    print('Queue Size:',myQueue.getSize())
```
```java
import java.util.NoSuchElementException;


class ArrayBasedQueue {

    /**
     * Array of objects
     */
    private Object[] array;

    /**
     * Size of queue
     */
    int size = 0;

    /**
     * Since it is a queue, we need track of both head and tail
     * Initial values to be 0
     */
    int head = 0;
    int tail = 0;

    /**
     * Constructor to create new array based queue
     * 
     * @param capacity
     */
    public ArrayBasedQueue(int capacity) {
        array = new Object[capacity];
    }

    /**
     * Method to push a new item in queue
     * We will deal only with tail while adding new item
     * 
     * @param item
     */
    public void enqueue(Object item) {
        if (size == array.length) {
            throw new IllegalStateException("Cannot add to full queue");
        }
        array[tail] = item;
        tail = (tail + 1) % array.length;
        size++;
    }

    /**
     * Method to pop a item from queue
     * We will deal only with head while deleting a element
     * 
     * @return {@link Object}
     */
    public Object dequeue() {
        if (size == 0) {
            throw new NoSuchElementException("Cannot remove from empty queue");
        }
        Object item = array[head];
        array[head] = null;
        head = (head + 1) % array.length;
        size--;
        return item;
    }

    /**
     * Method to check the top item in queue
     * 
     * @return {@link Object}
     */
    public Object peek() {
        if (size == 0) {
            throw new NoSuchElementException("Cannot peek from empty queue");
        }
        return array[head];
    }

    /**
     * Method to check size of queue
     * 
     * @return {@link int}
     */
    public int size() {
        return size;
    }

    /**
     * Method to check if queue is empty
     * 
     * @return {@link boolean}
     */
    public boolean isEmpty() {
        return size == 0;
    }

}

public class Main {

    public static void main(String[] args) {
        ArrayBasedQueue q = new ArrayBasedQueue(4);
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        q.enqueue(4);
        System.out.println(q.dequeue()); // 1
        System.out.println(q.dequeue()); // 2
        System.out.println(q.dequeue()); // 3
        System.out.println(q.dequeue()); // 4                        
    }
}
```
```java
import java.util.LinkedList;

class CustomQueue {

    private LinkedList<Object> queue;

    public CustomQueue() {
        this.queue = new LinkedList<>();
    }

    public void enqueue(Object item) {
        this.queue.addFirst(item);
    }

    public Object dequeue() {
        return this.queue.removeLast();
    }

    public Object peek() {
        return this.queue.getLast();
    }

    public int length() {
        return this.queue.size();
    }

    public boolean isEmpty() {
        return this.queue.isEmpty();
    }

    public static void main(String[] args) {
        CustomQueue q = new CustomQueue();
        q.enqueue(1);
        q.enqueue(2);
        System.out.println(q.dequeue()); // 1
        System.out.println(q.peek()); // 2
    }
}
```
```python
class CustomQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.insert(0, item)

    def dequeue(self):
        return self.queue.pop()

    def peek(self):
        return self.queue[-1]

    def length(self):
        return len(self.queue)

    def is_empty(self):
        return len(self.queue) == 0

queue = CustomQueue()
queue.enqueue(1)
queue.enqueue(2)
print(queue.dequeue())  # 1
print(queue.peek())    # 2
```
```cpp
#include <deque>
#include <iostream>

class CustomQueue {
private:
    std::deque<int> queue;

public:
    void enqueue(int item) {
        queue.push_front(item);
    }

    int dequeue() {
        int item = queue.back();
        queue.pop_back();
        return item;
    }

    int peek() {
        return queue.back();
    }

    size_t length() {
        return queue.size();
    }

    bool isEmpty() {
        return queue.empty();
    }
};

int main() {
    CustomQueue q;
    q.enqueue(1);
    q.enqueue(2);
    std::cout << q.dequeue() << "\n"; // 1
    std::cout << q.peek() << "\n";    // 2
}
```
```csharp
using System;
using System.Collections.Generic;

class CustomQueue {
    private LinkedList<Object> queue;

    public CustomQueue() {
        this.queue = new LinkedList<Object>();
    }

    public void Enqueue(Object item) {
        this.queue.AddFirst(item);
    }

    public Object Dequeue() {
        Object item = this.queue.Last.Value;
        this.queue.RemoveLast();
        return item;
    }

    public Object Peek() {
        return this.queue.Last.Value;
    }

    public int Length() {
        return this.queue.Count;
    }

    public bool IsEmpty() {
        return this.queue.Count == 0;
    }

    static void Main(string[] args) {
        CustomQueue q = new CustomQueue();
        q.Enqueue(1);
        q.Enqueue(2);
        Console.WriteLine(q.Dequeue()); // 1
        Console.WriteLine(q.Peek());    // 2
    }
}
```
```go
package main

import (
	"container/list"
	"fmt"
)

type CustomQueue struct {
	queue *list.List
}

func NewCustomQueue() *CustomQueue {
	return &CustomQueue{
		queue: list.New(),
	}
}

func (q *CustomQueue) Enqueue(item interface{}) {
	q.queue.PushFront(item)
}

func (q *CustomQueue) Dequeue() interface{} {
	item := q.queue.Back()
	q.queue.Remove(item)
	return item.Value
}

func (q *CustomQueue) Peek() interface{} {
	return q.queue.Back().Value
}

func (q *CustomQueue) Length() int {
	return q.queue.Len()
}

func (q *CustomQueue) IsEmpty() bool {
	return q.queue.Len() == 0
}

func main() {
	q := NewCustomQueue()
	q.Enqueue(1)
	q.Enqueue(2)
	fmt.Println(q.Dequeue()) // 1
	fmt.Println(q.Peek())    // 2
}
```

Stack

```js
class Stack {
  constructor() {
    this.stack = [];
  }

  push(item) {
    return this.stack.push(item);
  }

  pop() {
    return this.stack.pop();
  }

  peek() {
    return this.stack[this.length - 1];
  }

  get length() {
    return this.stack.length;
  }

  isEmpty() {
    return this.length === 0;
  }
}

const newStack = new Stack();
newStack.push(1);
newStack.push(2);
console.log(newStack);

newStack.pop();
console.log(newStack);

```
```py
class Stack(object):
    def __init__(self, limit=10):
        self.stack = []
        self.limit = limit

    # Printing the stack contents
    def __str__(self):
        return " ".join([str(i) for i in self.stack])

    # Pushing an element on to the stack
    def push(self, data):
        if len(self.stack) >= self.limit:
            print("Stack overflowed")
        else:
            self.stack.append(data)

    # Popping the top-most element
    def pop(self):
        if len(self.stack) <= 0:
            return -1
        else:
            return self.stack.pop()

    # Peeking the top-most element of the stack
    def peek(self):
        if len(self.stack) <= 0:
            return -1
        else:
            return self.stack[len(self.stack) - 1]

    # To check if stack is empty
    def is_empty(self):
        return self.stack == []

    # For checking the size of stack
    def size(self):
        return len(self.stack)


if __name__ == "__main__":
    my_stack = Stack()
    for i in range(10):
        my_stack.push(i)
    print(my_stack)
    my_stack.pop()  # popping the top element
    print(my_stack)
    my_stack.peek()  # printing the top element
    my_stack.is_empty()
    my_stack.size()

```
```java
class Stack {
    private String[] stack;
    private int top;

    public Stack(int size) {
        stack = new String[size];
        top = 0;
    }

    public void push(String value) {
        stack[top++] = value;
    }

    public void pop() {
        if (top > 0) {
            stack[--top] = null;
        }
    }

    public String peek() {
        if (top > 0) {
            return stack[top - 1];
        }
        return "";
    }

    public boolean isEmpty() {
        return top == 0;
    }

    public int length() {
        return top;
    }
}

public class Main {
    public static void main(String[] args) {
        Stack newStack = new Stack(10);
        newStack.push("1");
        newStack.push("2");
        System.out.println("Stack after pushing 1 and 2: " + newStack.length());
        newStack.pop();
        System.out.println("Top element after popping: " + newStack.peek());
    }
}
```
```cpp
#include <iostream>
#include <vector>
#include <string>

class Stack {
private:
    std::vector<std::string> stack;

public:
    void push(const std::string &item) {
        stack.push_back(item);
    }

    void pop() {
        if (!stack.empty()) {
            stack.pop_back();
        }
    }

    std::string peek() {
        if (!stack.empty()) {
            return stack.back();
        }
        return "";
    }

    bool isEmpty() {
        return stack.empty();
    }

    size_t length() {
        return stack.size();
    }
};

int main() {
    Stack newStack;
    newStack.push("1");
    newStack.push("2");
    newStack.pop();
    if (!newStack.peek().empty()) {
        std::cout << "Top element: " << newStack.peek() << std::endl;
    }
    return 0;
}
```
```csharp
using System;
using System.Collections.Generic;

public class Stack {
    private List<string> stack = new List<string>();

    public void Push(string item) {
        stack.Add(item);
    }

    public void Pop() {
        if (stack.Count > 0) {
            stack.RemoveAt(stack.Count - 1);
        }
    }

    public string Peek() {
        if (stack.Count > 0) {
            return stack[stack.Count - 1];
        }
        return "";
    }

    public bool IsEmpty() {
        return stack.Count == 0;
    }

    public int Length() {
        return stack.Count;
    }
}

public class Program {
    public static void Main(string[] args) {
        Stack newStack = new Stack();
        newStack.Push("1");
        newStack.Push("2");
        newStack.Pop();
        Console.WriteLine("Top element: " + newStack.Peek());
    }
}
```
```go
package main

import "fmt"

type Stack struct {
	stack []string
}

func (s *Stack) Push(item string) {
	s.stack = append(s.stack, item)
}

func (s *Stack) Pop() {
	if len(s.stack) > 0 {
		s.stack = s.stack[:len(s.stack)-1]
	}
}

func (s *Stack) Peek() string {
	if len(s.stack) > 0 {
		return s.stack[len(s.stack)-1]
	}
	return ""
}

func (s *Stack) IsEmpty() bool {
	return len(s.stack) == 0
}

func (s *Stack) Length() int {
	return len(s.stack)
}

func main() {
	newStack := &Stack{}
	newStack.Push("1")
	newStack.Push("2")
	newStack.Pop()
	fmt.Println("Top element:", newStack.Peek())
}
```

Hash Collision Check

True or False: a hash table can still have average O(1) lookup even though two different keys may produce the same hash bucket.

Hash Table

```js
class Hashmap {
  constructor() {
    this._storage = [];
  }

  hashStr(str) {
    let finalHash = 0;
    for (let i = 0; i < str.length; i++) {
      const charCode = str.charCodeAt(i);
      finalHash += charCode;
    }
    return finalHash;
  }

  set(key, val) {
    let idx = this.hashStr(key);

    if (!this._storage[idx]) {
      this._storage[idx] = [];
    }

    this._storage[idx].push([key, val]);
  }

  get(key) {
    let idx = this.hashStr(key);

    if (!this._storage[idx]) {
      return undefined;
    }

    for (let keyVal of this._storage[idx]) {
      if (keyVal[0] === key) {
        return keyVal[1];
      }
    }
  }
}

var dict = new Hashmap();
dict.set("james", "123-456-7890");
dict.set("jess", "213-559-6840");
console.log(dict.get("james"));

```
```py
class SimpleHashMap:
    def __init__(self):
        self.capacity = 10
        self.table = [None] * self.capacity

    def _hash_key(self, key):
        hash_val = 0
        for char in str(key):
            hash_val += ord(char)
        return hash_val % self.capacity

    def insert(self, key, value):
        hash_index = self._hash_key(key)
        key_value_pair = [key, value]

        if self.table[hash_index] is None:
            self.table[hash_index] = [key_value_pair]
            return True
        else:
            for pair in self.table[hash_index]:
                if pair[0] == key:
                    pair[1] = value
                    return True
            self.table[hash_index].append(key_value_pair)
            return True

    def retrieve(self, key):
        hash_index = self._hash_key(key)
        if self.table[hash_index] is not None:
            for pair in self.table[hash_index]:
                if pair[0] == key:
                    return pair[1]
        return None

    def remove(self, key):
        hash_index = self._hash_key(key)

        if self.table[hash_index] is None:
            return False
        for i in range(len(self.table[hash_index])):
            if self.table[hash_index][i][0] == key:
                self.table[hash_index].pop(i)
                return True
        return False

    def display(self):
        print("---PHONEBOOK---")
        for item in self.table:
            if item is not None:
                print(str(item))


phone_book = SimpleHashMap()
phone_book.insert("Alice", "555-1234")
phone_book.insert("Bob", "555-5678")
phone_book.insert("Alice", "555-9999")
phone_book.display()
phone_book.remove("Alice")
phone_book.display()
print("Bob: " + phone_book.retrieve("Bob"))
```
```java
import java.util.ArrayList;

class MyHashMap {

    private class Pair {
        String key;
        String value;
        Pair next;

        Pair(String k, String v, Pair n) {
            this.key = k;
            this.value = v;
            this.next = n;
        }
    }

    private final int SIZE = 10;
    private final ArrayList<Pair> buckets;

    public MyHashMap() {
        this.buckets = new ArrayList<>(SIZE);
        for (int i = 0; i < SIZE; i++) {
            buckets.add(null);
        }
    }

    private int hash(String key) {
        return Math.abs(key.hashCode() % SIZE);
    }

    public boolean insert(String key, String value) {
        int index = hash(key);
        Pair bucket = buckets.get(index);
        if (bucket == null) {
            buckets.set(index, new Pair(key, value, null));
            return true;
        } else {
            Pair newPair = new Pair(key, value, bucket);
            buckets.set(index, newPair);
            return true;
        }
    }

    public String retrieve(String key) throws Exception {
        int index = hash(key);
        Pair bucket = buckets.get(index);
        while (bucket != null) {
            if (bucket.key.equals(key)) {
                return bucket.value;
            }
            bucket = bucket.next;
        }
        throw new Exception("Key not found");
    }

    public boolean delete(String key) {
        int index = hash(key);
        Pair bucket = buckets.get(index);
        Pair prev = null;
        while (bucket != null) {
            if (bucket.key.equals(key)) {
                if (prev == null) {
                    buckets.set(index, bucket.next);
                } else {
                    prev.next = bucket.next;
                    bucket.next = null;
                }
                return true;
            }
            prev = bucket;
            bucket = bucket.next;
        }
        return false;
    }
}

public class MainExample {

    public static void main(String[] args) {
        MyHashMap map = new MyHashMap();
        map.insert("key1", "value1");
        map.insert("key2", "value2");
        try {
            System.out.println(map.retrieve("key2"));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
```
```cpp
#include <iostream>
#include <vector>
#include <string>

class HashMap {
private:
    struct KeyValue {
        std::string key;
        std::string value;
        KeyValue* next = nullptr;

        KeyValue(std::string k, std::string v, KeyValue* n) : key(k), value(v), next(n) {}
    };

    std::vector<KeyValue*> map;
    static const int BUCKET_SIZE = 10;

    int getHash(std::string key) {
        int hash = std::hash<std::string>{}(key);
        return abs(hash % BUCKET_SIZE);
    }

public:
    HashMap() {
        map.resize(BUCKET_SIZE, nullptr);
    }

    bool add(std::string key, std::string val) {
        int hash = getHash(key);

        if (map[hash] == nullptr) {
            map[hash] = new KeyValue(key, val, nullptr);
        } else {
            KeyValue* temp = new KeyValue(key, val, map[hash]);
            map[hash] = temp;
        }

        return true;
    }

    std::string get(std::string key) {
        int hash = getHash(key);

        if (map[hash] != nullptr) {
            KeyValue* temp = map[hash];
            while (temp != nullptr) {
                if (temp->key == key) {
                    return temp->value;
                }
                temp = temp->next;
            }
        }

        return "Specified key doesn't exist";
    }

    bool remove(std::string key) {
        int hash = getHash(key);

        if (map[hash] != nullptr) {
            KeyValue* temp = map[hash];
            KeyValue* parent = nullptr;

            while (temp != nullptr) {
                if (temp->key == key) {
                    if (parent == nullptr) {
                        map[hash] = temp->next;
                    } else {
                        parent->next = temp->next;
                        delete temp;
                    }
                    return true;
                }
                temp = temp->next;
            }
        }

        return false;
    }
};

int main() {
    HashMap abc;

    abc.add("abc", "def");
    abc.add("abdefc", "askjfhdjf");

    std::cout << abc.get("abdefc") << std::endl;

    return 0;
}
```
```csharp
using System;
using System.Collections.Generic;

class HashMap {
    private class KeyValue {
        public string Key { get; }
        public string Value { get; set; }
        public KeyValue Next { get; set; }

        public KeyValue(string key, string value, KeyValue next) {
            Key = key;
            Value = value;
            Next = next;
        }
    }

    private readonly List<KeyValue> map = new List<KeyValue>();
    private const int BUCKET_SIZE = 10;

    public HashMap() {
        for (int i = 0; i < BUCKET_SIZE; i++) {
            map.Add(null);
        }
    }

    private int GetHash(string key) {
        int hash = key.GetHashCode();
        hash = Math.Abs(hash % BUCKET_SIZE);
        return hash;
    }

    public bool Add(string key, string val) {
        int hash = GetHash(key);

        if (map[hash] == null) {
            map[hash] = new KeyValue(key, val, null);
        } else {
            KeyValue temp = new KeyValue(key, val, map[hash]);
            map[hash] = temp;
        }
        return true;
    }

    public string Get(string key) {
        int hash = GetHash(key);

        if (map[hash] != null) {
            KeyValue temp = map[hash];
            while (temp != null) {
                if (temp.Key.Equals(key)) {
                    return temp.Value;
                }
                temp = temp.Next;
            }
        }

        return "Specified key doesn't exist";
    }

    public bool Remove(string key) {
        int hash = GetHash(key);

        if (map[hash] != null) {
            KeyValue temp = map[hash];
            KeyValue parent = null;

            while (temp != null) {
                if (temp.Key.Equals(key)) {
                    if (parent == null) {
                        map[hash] = temp.Next;
                    } else {
                        parent.Next = temp.Next;
                        // delete temp
                        temp.Next = null;
                    }
                    return true;
                }
                temp = temp.Next;
            }
        }

        return false;
    }

    public static void Main(string[] args) {
        HashMap abc = new HashMap();

        abc.Add("abc", "def");
        abc.Add("abdefc", "askjfhdjf");

        Console.WriteLine(abc.Get("abdefc"));
    }
}
```
```go
package main

import (
	"fmt"
	"math"
)

type KeyValue struct {
	key  string
	val  string
	next *KeyValue
}

type HashMap struct {
	map         []*KeyValue
	BUCKET_SIZE int
}

func NewHashMap() *HashMap {
	h := &HashMap{
		BUCKET_SIZE: 10,
	}
	h.map = make([]*KeyValue, h.BUCKET_SIZE)
	return h
}

func (h *HashMap) getHash(key string) int {
	hash := 0
	for _, char := range key {
		hash += int(char)
	}
	return int(math.Abs(float64(hash % h.BUCKET_SIZE)))
}

func (h *HashMap) Add(key, val string) bool {
	hash := h.getHash(key)

	if h.map[hash] == nil {
		h.map[hash] = &KeyValue{key: key, val: val, next: nil}
	} else {
		temp := &KeyValue{key: key, val: val, next: h.map[hash]}
		h.map[hash] = temp
	}

	return true
}

func (h *HashMap) Get(key string) string {
	hash := h.getHash(key)

	if h.map[hash] != nil {
		temp := h.map[hash]
		for temp != nil {
			if temp.key == key {
				return temp.val
			}
			temp = temp.next
		}
	}

	return "Specified key doesn't exist"
}

func (h *HashMap) Remove(key string) bool {
	hash := h.getHash(key)

	if h.map[hash] != nil {
		temp := h.map[hash]
		var parent *KeyValue = nil

		for temp != nil {
			if temp.key == key {
				if parent == nil {
					h.map[hash] = temp.next
				} else {
					parent.next = temp.next
					temp.next = nil
				}
				return true
			}
			temp = temp.next
		}
	}

	return false
}

func main() {
	abc := NewHashMap()

	abc.Add("abc", "def")
	abc.Add("abdefc", "askjfhdjf")

	fmt.Println(abc.Get("abdefc"))
}
```

Graph

```js
class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(nodeVal) {
    this.adjacencyList[nodeVal] = [];
  }

  addEdge(src, dest) {
    this.adjacencyList[src].push(dest);
    this.adjacencyList[dest].push(src);
  }

  removeVertex(val) {
    if (this.adjacencyList[val]) {
      this.adjacencyList.delete(val);
    }

    this.adjacencyList.forEach((vertex) => {
      const neighborIdx = vertex.indexOf(val);
      if (neighborIdx >= 0) {
        vertex.splice(neighborIdx, 1);
      }
    });
  }

  removeEdge(src, dest) {
    const srcDestIdx = this.adjacencyList[src].indexOf(dest);
    this.adjacencyList[src].splice(srcDestIdx, 1);

    const destSrcIdx = this.adjacencyList[dest].indexOf(src);
    this.adjacencyList[dest].splice(destSrcIdx, 1);
  }
}

var graph = new Graph(7);
var vertices = ["A", "B", "C", "D", "E", "F", "G"];
for (var i = 0; i < vertices.length; i++) {
  graph.addVertex(vertices[i]);
}
graph.addEdge("A", "G");
graph.addEdge("A", "E");
graph.addEdge("A", "C");
graph.addEdge("B", "C");
graph.addEdge("C", "D");
graph.addEdge("D", "E");
graph.addEdge("E", "F");
graph.addEdge("E", "C");
graph.addEdge("G", "D");
console.log(graph.adjacencyList);

```
```py
class GraphStructure:
    def __init__(self):
        self.node_links = {}

    def add_node(self, node_label):
        self.node_links[node_label] = []

    def connect_nodes(self, node1, node2):
        self.node_links[node1].append(node2)
        self.node_links[node2].append(node1)

    def remove_node(self, node):
        if node in self.node_links:
            del self.node_links[node]

        for vertex in self.node_links.values():
            vertex.remove(node) if node in vertex else None

    def disconnect_nodes(self, node1, node2):
        self.node_links[node1].remove(node2)
        self.node_links[node2].remove(node1)

if __name__ == '__main__':
    my_graph = GraphStructure()
    vertices = ["A", "B", "C", "D", "E", "F", "G"]
    for vertex in vertices:
        my_graph.add_node(vertex)

    my_graph.connect_nodes("A", "G")
    my_graph.connect_nodes("A", "E")
    my_graph.connect_nodes("A", "C")
    my_graph.connect_nodes("B", "C")
    my_graph.connect_nodes("C", "D")
    my_graph.connect_nodes("D", "E")
    my_graph.connect_nodes("E", "F")
    my_graph.connect_nodes("E", "C")
    my_graph.connect_nodes("G", "D")

    print(my_graph.node_links)

```
```java
import java.util.HashSet;
import java.util.LinkedList;

class Node {
    private String name;
    private LinkedList < Edge > edgeList;

    public Node(String name) {
        this.name = name;
        edgeList = new LinkedList < > ();
    }

    public String getName() {
        return name;
    }

    public LinkedList < Edge > getEdges() {
        return edgeList;
    }
}

class Edge {
    private int weight;
    private Node destVertex;

    public Edge(Node dest, int w) {
        this.destVertex = dest;
        this.weight = w;
    }

    public Edge(Node dest) {
        this.destVertex = dest;
        this.weight = 1;
    }

    public int getWeight() {
        return weight;
    }

    public Node getDestVertex() {
        return destVertex;
    }
}

class Graph {
    private HashSet < Node > nodes;

    public Graph() {
        nodes = new HashSet < > ();
    }

    public boolean AddEdge(Node v1, Node v2, int weight) {
        return v1.getEdges().add(new Edge(v2, weight)) && v2.getEdges().add(new Edge(v1, weight));
    }

    public boolean AddVertex(Node v) {
        return nodes.add(v);
    }

    public void printGraph() {
        for (Node v: nodes) {
            System.out.print("vertex name: " + v.getName() + ":\n");
            for (Edge e: v.getEdges()) {
                System.out.print("destVertex: " + e.getDestVertex().getName() + ", weight: " + e.getWeight() + "\n");
            }
            System.out.print("\n");
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph ourGraph = new Graph();

        // nodes
        Node v0 = new Node("0");
        Node v1 = new Node("1");
        Node v2 = new Node("2");
        Node v3 = new Node("3");

        ourGraph.AddVertex(v0);
        ourGraph.AddVertex(v1);
        ourGraph.AddVertex(v2);
        ourGraph.AddVertex(v3);

        // edges
        ourGraph.AddEdge(v0, v1, 2);
        ourGraph.AddEdge(v1, v2, 3);
        ourGraph.AddEdge(v2, v0, 1);
        ourGraph.AddEdge(v2, v3, 1);
        ourGraph.AddEdge(v3, v2, 4);

        ourGraph.printGraph();
    }
}
```
```go
package main

import "fmt"

type Graph struct {
    AdjacencyList map[string][]string
}

func NewGraph() *Graph {
    return &Graph{AdjacencyList: make(map[string][]string)}
}

func (g *Graph) AddVertex(vertex string) {
    g.AdjacencyList[vertex] = []string{}
}

func (g *Graph) AddEdge(src, dest string) {
    g.AdjacencyList[src] = append(g.AdjacencyList[src], dest)
    g.AdjacencyList[dest] = append(g.AdjacencyList[dest], src)
}

func (g *Graph) RemoveVertex(vertex string) {
    delete(g.AdjacencyList, vertex)
    for k, v := range g.AdjacencyList {
        for i, neighbor := range v {
            if neighbor == vertex {
                g.AdjacencyList[k] = append(v[:i], v[i+1:]...)
            }
        }
    }
}

func (g *Graph) RemoveEdge(src, dest string) {
    removeEdgeHelper(g.AdjacencyList, src, dest)
    removeEdgeHelper(g.AdjacencyList, dest, src)
}

func removeEdgeHelper(adjList map[string][]string, src, dest string) {
    for i, neighbor := range adjList[src] {
        if neighbor == dest {
            adjList[src] = append(adjList[src][:i], adjList[src][i+1:]...)
        }
    }
}

func main() {
    g := NewGraph()
    vertices := []string{"A", "B", "C", "D", "E", "F", "G"}
    for _, vertex := range vertices {
        g.AddVertex(vertex)
    }
    g.AddEdge("A", "G")
    g.AddEdge("A", "E")
    g.AddEdge("A", "C")
    g.AddEdge("B", "C")
    g.AddEdge("C", "D")
    g.AddEdge("D", "E")
    g.AddEdge("E", "F")
    g.AddEdge("E", "C")
    g.AddEdge("G", "D")

    fmt.Println(g.AdjacencyList)
}

```
```cpp
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

class Graph {
private:
    std::unordered_map<std::string, std::vector<std::string>> AdjacencyList;

public:
    Graph() {
        // Initialize an empty adjacency list
        AdjacencyList = {};
    }

    void AddVertex(std::string vertex) {
        AdjacencyList[vertex] = {};
    }

    void AddEdge(std::string src, std::string dest) {
        AdjacencyList[src].push_back(dest);
        AdjacencyList[dest].push_back(src);
    }

    void RemoveVertex(std::string vertex) {
        AdjacencyList.erase(vertex);
        for (auto& [key, neighbors] : AdjacencyList) {
            neighbors.erase(std::remove(neighbors.begin(), neighbors.end(), vertex), neighbors.end());
        }
    }

    void RemoveEdge(std::string src, std::string dest) {
        removeEdgeHelper(AdjacencyList[src], dest);
        removeEdgeHelper(AdjacencyList[dest], src);
    }

private:
    void removeEdgeHelper(std::vector<std::string>& adjList, std::string dest) {
        adjList.erase(std::remove(adjList.begin(), adjList.end(), dest), adjList.end());
    }
};

public class Main {
  int main() {
      Graph g;
      std::vector<std::string> vertices = {"A", "B", "C", "D", "E", "F", "G"};

      for (const auto& vertex : vertices) {
          g.AddVertex(vertex);
      }

      g.AddEdge("A", "G");
      g.AddEdge("A", "E");
      g.AddEdge("A", "C");
      g.AddEdge("B", "C");
      g.AddEdge("C", "D");
      g.AddEdge("D", "E");
      g.AddEdge("E", "F");
      g.AddEdge("E", "C");
      g.AddEdge("G", "D");
  
      // For demonstration purposes, you might want to print the adjacency list here.
  
      return 0;
  }
}

```
```csharp
using System;
using System.Collections.Generic;

class Graph {
    private Dictionary<string, List<string>> AdjacencyList;

    public Graph() {
        // Initialize an empty adjacency list
        AdjacencyList = new Dictionary<string, List<string>>();
    }

    public void AddVertex(string vertex) {
        AdjacencyList[vertex] = new List<string>();
    }

    public void AddEdge(string src, string dest) {
        AdjacencyList[src].Add(dest);
        AdjacencyList[dest].Add(src);
    }

    public void RemoveVertex(string vertex) {
        AdjacencyList.Remove(vertex);
        foreach (var neighbors in AdjacencyList.Values) {
            neighbors.Remove(vertex);
        }
    }

    public void RemoveEdge(string src, string dest) {
        RemoveEdgeHelper(AdjacencyList[src], dest);
        RemoveEdgeHelper(AdjacencyList[dest], src);
    }

    private void RemoveEdgeHelper(List<string> adjList, string dest) {
        adjList.Remove(dest);
    }
}

class Program {
    static void Main(string[] args) {
        Graph g = new Graph();
        string[] vertices = {"A", "B", "C", "D", "E", "F", "G"};

        foreach (string vertex in vertices) {
            g.AddVertex(vertex);
        }

        g.AddEdge("A", "G");
        g.AddEdge("A", "E");
        g.AddEdge("A", "C");
        g.AddEdge("B", "C");
        g.AddEdge("C", "D");
        g.AddEdge("D", "E");
        g.AddEdge("E", "F");
        g.AddEdge("E", "C");
        g.AddEdge("G", "D");

        // For demonstration purposes, you might want to print the adjacency list here.
    }
}
```

BST Traversal Check

For a valid binary search tree, which traversal visits the values in sorted order?

Tree

```javascript
function TreeNode(value) {
  this.value = value;
  this.children = [];
  this.parent = null;

  this.setParentNode = function (node) {
    this.parent = node;
  };

  this.getParentNode = function () {
    return this.parent;
  };

  this.addNode = function (node) {
    node.setParentNode(this);
    this.children[this.children.length] = node;
  };

  this.getChildren = function () {
    return this.children;
  };

  this.removeChildren = function () {
    this.children = [];
  };
}

const root = new TreeNode(1);
root.addNode(new TreeNode(2));
root.addNode(new TreeNode(3));

const children = root.getChildren();
for (let i = 0; i < children.length; i++) {
  for (let j = 0; j < 5; j++) {
    children[i].addNode(new TreeNode("second level child " + j));
  }
}

console.log(root);
children[0].removeChildren();
console.log(root);
console.log(root.getParentNode());
console.log(children[1].getParentNode());
```
```python
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []
        self.parent = None

    def set_parent_node(self, node):
        self.parent = node

    def get_parent_node(self):
        return self.parent

    def add_node(self, node):
        node.set_parent_node(self)
        self.children.append(node)

    def get_children(self):
        return self.children

    def remove_children(self):
        self.children = []


root = TreeNode(1)
root.add_node(TreeNode(2))
root.add_node(TreeNode(3))

children = root.get_children()
for i in range(len(children)):
    for j in range(5):
        children[i].add_node(TreeNode(f"second level child {j}"))

print(root.__dict__)
children[0].remove_children()
print(root.__dict__)
print(root.get_parent_node())
print(children[1].get_parent_node())
```
```java
import java.util.ArrayList;

class TreeNode<T> {
    private T value;
    private ArrayList<TreeNode<T>> children = new ArrayList<>();
    private TreeNode<T> parent = null;

    public TreeNode(T value) {
        this.value = value;
    }

    public void setParentNode(TreeNode<T> node) {
        this.parent = node;
    }

    public TreeNode<T> getParentNode() {
        return this.parent;
    }

    public void addNode(TreeNode<T> node) {
        node.setParentNode(this);
        this.children.add(node);
    }

    public ArrayList<TreeNode<T>> getChildren() {
        return this.children;
    }

    public void removeChildren() {
        this.children = new ArrayList<>();
    }
}

public class Main {
    public static void main(String[] args) {
        TreeNode<Integer> root = new TreeNode<>(1);
        root.addNode(new TreeNode<>(2));
        root.addNode(new TreeNode<>(3));

        ArrayList<TreeNode<Integer>> children = root.getChildren();
        for (int i = 0; i < children.size(); i++) {
            for (int j = 0; j < 5; j++) {
                children.get(i).addNode(new TreeNode<>("second level child " + j));
            }
        }

        System.out.println(root);
        children.get(0).removeChildren();
        System.out.println(root);
        System.out.println(root.getParentNode());
        System.out.println(children.get(1).getParentNode());
    }
}
```
```cpp
#include <iostream>
#include <vector>
#include <string>

template <typename T>
class TreeNode {
    T value;
    std::vector<TreeNode*> children;
    TreeNode* parent = nullptr;

public:
    TreeNode(T value) : value(value) {}

    void setParentNode(TreeNode* node) {
        this->parent = node;
    }

    TreeNode* getParentNode() {
        return this->parent;
    }

    void addNode(TreeNode* node) {
        node->setParentNode(this);
        this->children.push_back(node);
    }

    std::vector<TreeNode*> getChildren() {
        return this->children;
    }

    void removeChildren() {
        this->children.clear();
    }
};

int main() {
    TreeNode<int> root(1);
    root.addNode(new TreeNode<int>(2));
    root.addNode(new TreeNode<int>(3));

    std::vector<TreeNode<int>*> children = root.getChildren();
    for (int i = 0; i < children.size(); i++) {
        for (int j = 0; j < 5; j++) {
            children[i]->addNode(new TreeNode<std::string>("second level child " + std::to_string(j)));
        }
    }

    // Further code to print or interact with the structure.
    return 0;
}
```
```csharp
using System;
using System.Collections.Generic;

class TreeNode<T> {
    public T value;
    public List<TreeNode<T>> children = new List<TreeNode<T>>();
    public TreeNode<T> parent = null;

    public TreeNode(T value) {
        this.value = value;
    }

    public void SetParentNode(TreeNode<T> node) {
        this.parent = node;
    }

    public TreeNode<T> GetParentNode() {
        return this.parent;
    }

    public void AddNode(TreeNode<T> node) {
        node.SetParentNode(this);
        this.children.Add(node);
    }

    public List<TreeNode<T>> GetChildren() {
        return this.children;
    }

    public void RemoveChildren() {
        this.children.Clear();
    }
}

class Program {
    static void Main(string[] args) {
        TreeNode<int> root = new TreeNode<int>(1);
        root.AddNode(new TreeNode<int>(2));
        root.AddNode(new TreeNode<int>(3));

        List<TreeNode<int>> children = root.GetChildren();
        for (int i = 0; i < children.Count; i++) {
            for (int j = 0; j < 5; j++) {
                children[i].AddNode(new TreeNode<string>("second level child " + j));
            }
        }

        // Further code to print or interact with the structure.
    }
}
```
```go
package main

import (
	"fmt"
)

type TreeNode struct {
	value    interface{}
	children []*TreeNode
	parent   *TreeNode
}

func (n *TreeNode) setParentNode(node *TreeNode) {
	n.parent = node
}

func (n *TreeNode) getParentNode() *TreeNode {
	return n.parent
}

func (n *TreeNode) addNode(node *TreeNode) {
	node.setParentNode(n)
	n.children = append(n.children, node)
}

func (n *TreeNode) getChildren() []*TreeNode {
	return n.children
}

func (n *TreeNode) removeChildren() {
	n.children = []*TreeNode{}
}

func main() {
	root := &TreeNode{value: 1}
	root.addNode(&TreeNode{value: 2})
	root.addNode

(&TreeNode{value: 3})

	children := root.getChildren()
	for i := 0; i < len(children); i++ {
		for j := 0; j < 5; j++ {
			children[i].addNode(&TreeNode{value: "second level child " + fmt.Sprint(j)})
		}
	}

	// Further code to print or interact with the structure.
}
```

Binary Search Tree

```js
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

class BST {
  constructor(val) {
    this.root = new Node(val);
  }

  add(val) {
    let newNode = new Node(val);

    function findPosAndInsert(currNode, newNode) {
      if (newNode.val < currNode.val) {
        if (!currNode.left) {
          currNode.left = newNode;
        } else {
          findPosAndInsert(currNode.left, newNode);
        }
      } else {
        if (!currNode.right) {
          currNode.right = newNode;
        } else {
          findPosAndInsert(currNode.right, newNode);
        }
      }
    }

    if (!this.root) {
      this.root = newNode;
    } else {
      findPosAndInsert(this.root, newNode);
    }
  }

  remove(val) {
    let self = this;
    let removeNode = function (node, val) {
      if (!node) {
        return null;
      }
      if (val === node.val) {
        if (!node.left && !node.right) {
          return null;
        }
        if (!node.left) {
          return node.right;
        }
        if (!node.right) {
          return node.left;
        }
        let temp = self.getMinimum(node.right);
        node.val = temp;
        node.right = removeNode(node.right, temp);
        return node;
      } else if (val < node.val) {
        node.left = removeNode(node.left, val);
        return node;
      } else {
        node.right = removeNode(node.right, val);
        return node;
      }
    };
    this.root = removeNode(this.root, val);
  }

  getMinimum(node) {
    if (!node) {
      node = this.root;
    }
    while (node.left) {
      node = node.left;
    }
    return node.val;
  }

  // helper method
  contains(value) {
    let doesContain = false;

    function traverse(bst) {
      if (this.root.value === value) {
        doesContain = true;
      } else if (this.root.left !== undefined && value < this.root.value) {
        traverse(this.root.left);
      } else if (this.root.right !== undefined && value > this.root.value) {
        traverse(this.root.right);
      }
    }

    traverse(this);
    return doesContain;
  }
}

const bst = new BST(4);
bst.add(3);
bst.add(5);
bst.remove(3);
console.log(bst);

```
```py
class Node(object):
    def __init__(self, val):
        self.val = val
        self.left_child = None
        self.right_child = None

    def insert(self, val):
        """For inserting the value in the Tree"""
        if self.val == val:
            return False  # A BST cannot contain duplicate data

        elif val < self.val:
            """Values less than the root data are placed to the left of the root"""
            if self.left_child:
                return self.left_child.insert(val)
            else:
                self.left_child = Node(val)
                return True

        else:
            """Values greater than the root data are placed to the right of the root"""
            if self.right_child:
                return self.right_child.insert(val)
            else:
                self.right_child = Node(val)
                return True

    def min_node(self, node):
        current = node

        # Find the leftmost leaf
        while current.left_child is not None:
            current = current.left_child

        return current

    def max_node(self, node):
        current = node

        # Find the leftmost leaf
        while current.right_child is not None:
            current = current.right_child

        return current

    def delete(self, val, root):
        """For deleting the node"""
        if self is None:
            return None

        # If current node's data is less than that of root node,
        # then only search in left subtree, otherwise search in right subtree
        if val < self.val:
            self.left_child = self.left_child.delete(val, root)
        elif val > self.val:
            self.right_child = self.right_child.delete(val, root)
        else:
            # Deleting node with one child
            if self.left_child is None:

                if self == root:
                    temp = self.min_node(self.right_child)
                    self.val = temp.val
                    self.right_child = self.right_child.delete(temp.val, root)

                temp = self.right_child
                self = None
                return temp
            elif self.right_child is None:

                if self == root:
                    temp = self.max_node(self.left_child)
                    self.val = temp.val
                    self.left_child = self.left_child.delete(temp.val, root)

                temp = self.left_child
                self = None
                return temp

            # Deleting node with two children
            # First get the in-order successor
            temp = self.min_node(self.right_child)
            self.val = temp.val
            self.right_child = self.right_child.delete(temp.val, root)

        return self

    def find(self, val):
        """This function checks whether the specified val is in tree or not"""
        if val == self.val:
            return True
        elif val < self.val:
            if self.left_child:
                return self.left_child.find(val)
            else:
                return False
        else:
            if self.right_child:
                return self.right_child.find(val)
            else:
                return False

    def preorder(self):
        """For preorder traversal of the BST"""
        if self:
            print(str(self.val), end=" ")
            if self.left_child:
                self.left_child.preorder()
            if self.right_child:
                self.right_child.preorder()

    def inorder(self):
        """For Inorder traversal of the BST"""
        if self:
            if self.left_child:
                self.left_child.inorder()
            print(str(self.val), end=" ")
            if self.right_child:
                self.right_child.inorder()

    def postorder(self):
        """For postorder traversal of the BST"""
        if self:
            if self.left_child:
                self.left_child.postorder()
            if self.right_child:
                self.right_child.postorder()
            print(str(self.val), end=" ")


class Tree(object):
    def __init__(self):
        self.root = None

    def insert(self, val):
        if self.root:
            return self.root.insert(val)
        else:
            self.root = Node(val)
            return True

    def delete(self, val):
        if self.root is not None:
            return self.root.delete(val, self.root)

    def find(self, val):
        if self.root:
            return self.root.find(val)
        else:
            return False

    def preorder(self):
        if self.root is not None:
            print()
            print("Preorder: ")
            self.root.preorder()

    def inorder(self):
        print()
        if self.root is not None:
            print("Inorder: ")
            self.root.inorder()

    def postorder(self):
        print()
        if self.root is not None:
            print("Postorder: ")
            self.root.postorder()


if __name__ == "__main__":
    tree = Tree()
    tree.insert(11)
    tree.insert(9)
    tree.insert(6)
    tree.insert(3)
    tree.insert(17)
    tree.insert(5)
    tree.insert(4)
    tree.insert(19)
    tree.insert(12)
    print(tree.find(13))
    print(tree.find(5))
    """ The following tree is generated:
                    11
                 /     \
               6        9
              /           \
            3              17
             \             /  \
              5          12    19
             /
            4
    """

    tree.preorder()
    tree.inorder()
    tree.postorder()
    print("\n\nAfter deleting 19")
    tree.delete(19)
    tree.inorder()
    tree.preorder()
    print("\n\nAfter deleting 12")
    tree.delete(12)
    tree.inorder()
    tree.preorder()
```
```java
class Tree {
    private Node rootNode;

    /**
     * Create new Node with value and insert into this Tree
     * @param value Initial value for new Node
     */
    public void insertValue(int value) {
        insertNode(new Node(value));
    }

    /**
     * Insert new Node into this Tree
     * @param newNode Node to be inserted into this Tree
     */
    public void insertNode(Node newNode) {
        if (rootNode == null) {
            rootNode = new Node(newNode.getValue());
        } else {
            insertNode(rootNode, newNode);
        }
    }

    /**
     * Search this tree for a value
     *
     * @param value Value to be searched in this Tree
     * @return True if this tree contains value
     */
    public boolean containsValue(int value) {
        if (getNode(rootNode, value) == null) {
            return false;
        }
        return true;
    }

    /** 
     * Get Node in this Tree that contains value
     *
     * @param value Value to be searched within this Tree
     * @return Node that matches value or null if no match found
     */
    public Node getNode(Node currNode, int value) {
        if (currNode == null)
            return null;
        if (currNode.getValue() == value)
            return currNode;
        if (value < currNode.getValue())
            return getNode(currNode.getleft(), value);
        return getNode(currNode.getright(), value);
    }

    /**
     * Insert a new node into this tree
     *
     * @param currNode Current node we are comparing to newNode
     * @param newNode     New node that is to be inserted
     */
    private void insertNode(Node currNode, Node newNode) {
        if (newNode.getValue() < currNode.getValue()) {
            if (currNode.getleft() == null)
                currNode.setleft(newNode);
            else
                insertNode(currNode.getleft(), newNode);
        }
        if (newNode.getValue() > currNode.getValue()) {
            if (currNode.getright() == null)
                currNode.setright(newNode);
            else
                insertNode(currNode.getright(), newNode);
        }
    }

    /**
     * @return String representation of this Tree
     */
    @Override
    public String toString() {
        if (rootNode != null) {
            return rootNode.toString();
        }
        return "";
    }
}

class Node {
    private Node left;
    private Node right;
    private int value;

    /**
     * Node constructor with initial Node value
     *
     * @param value Initial value for this node
     */
    public Node(int value) {
        left = null;
        right = null;
        this.value = value;
    }

    /**
     * Set left node pointer for this Node
     *
     * @param node Left node for this Node
     */
    public void setleft(Node node) {
        this.left = node;
    }
    /**
     * Set right node pointer for this Node
     *
     * @param node Right node for this Node
     */
    public void setright(Node node) {
        this.right = node;
    }
    /**
     * Set value for this Node
     *
     * @param value Value for this Node
     */
    public void setValue(int value) {
        this.value = value;
    }

    /**
     * @return Left node for this Node
     */
    public Node getleft() {
        return left;
    }
    /**
     * @return Right node for this Node
     */
    public Node getright() {
        return right;
    }
    /**
     * @return Current value for this Node
     */
    public int getValue() {
        return value;
    }

    /**
     * @return String representation of this Node
     */
    @Override
    public String toString() {
        String result = value + "";
        if (left != null) result = left.toString() + " - " + result;
        if (right != null) result = result + " - " + right.toString();
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Tree myTree = new Tree();
        myTree.insertValue(20);
        myTree.insertValue(9);
        myTree.insertValue(13);
        myTree.insertValue(21);
        myTree.insertValue(14);
        System.out.println(myTree.toString());
        System.out.println(myTree.containsValue(20));
        System.exit(0);
    }
}
```
```cpp
#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int value;
    Node* left;
    Node* right;
    Node(int val) : value(val), left(nullptr), right(nullptr) {}
};

class Tree {
private:
    Node* rootNode;

public:
    Tree() : rootNode(nullptr) {}

    void insertValue(int value) {
        insertNode(new Node(value));
    }

    void insertNode(Node* newNode) {
        if (rootNode == nullptr) {
            rootNode = newNode;
        } else {
            insertNode(rootNode, newNode);
        }
    }

    bool containsValue(int value) {
        return getNode(rootNode, value) != nullptr;
    }

    Node* getNode(Node* currNode, int value) {
        if (currNode == nullptr) return nullptr;
        if (currNode->value == value) return currNode;
        if (value < currNode->value) return getNode(currNode->left, value);
        return getNode(currNode->right, value);
    }

private:
    void insertNode(Node* currNode, Node* newNode) {
        if (newNode->value < currNode->value) {
            if (currNode->left == nullptr)
                currNode->left = newNode;
            else
                insertNode(currNode->left, newNode);
        }
        if (newNode->value > currNode->value) {
            if (currNode->right == nullptr)
                currNode->right = newNode;
            else
                insertNode(currNode->right, newNode);
        }
    }
};

// Added main function
int main() {
    Tree myTree;

    // Insert values
    myTree.insertValue(5);
    myTree.insertValue(2);
    myTree.insertValue(8);
    myTree.insertValue(1);
    myTree.insertValue(3);

    // Check if the tree contains a value
    cout << "Does the tree contain 3? " << (myTree.containsValue(3) ? "Yes" : "No") << endl;
    cout << "Does the tree contain 9? " << (myTree.containsValue(9) ? "Yes" : "No") << endl;

    return 0;
}
```
```csharp
class Node {
    public int value;
    public Node left;
    public Node right;
    
    public Node(int val) {
        value = val;
        left = null;
        right = null;
    }
}

class Tree {
    private Node rootNode;

    public void InsertValue(int value) {
        InsertNode(new Node(value));
    }

    public void InsertNode(Node newNode) {
        if (rootNode == null) {
            rootNode = newNode;
        } else {
            InsertNode(rootNode, newNode);
        }
    }

    public bool ContainsValue(int value) {
        return GetNode(rootNode, value) != null;
    }

    private Node GetNode(Node currNode, int value) {
        if (currNode == null) return null;
        if (currNode.value == value) return currNode;
        if (value < currNode.value) return GetNode(currNode.left, value);
        return GetNode(currNode.right, value);
    }

    private void InsertNode(Node currNode, Node newNode) {
        if (newNode.value < currNode.value) {
            if (currNode.left == null)
                currNode.left = newNode;
            else
                InsertNode(currNode.left, newNode);
        }
        if (newNode.value > currNode.value) {
            if (currNode.right == null)
                currNode.right = newNode;
            else
                InsertNode(currNode.right, newNode);
        }
    }
}

```
```go
type Node struct {
    Value int
    Left  *Node
    Right *Node
}

type Tree struct {
    RootNode *Node
}

func (tree *Tree) InsertValue(value int) {
    newNode := &Node{Value: value}
    tree.InsertNode(newNode)
}

func (tree *Tree) InsertNode(newNode *Node) {
    if tree.RootNode == nil {
        tree.RootNode = newNode
    } else {
        insertNode(tree.RootNode, newNode)
    }
}

func insertNode(currNode *Node, newNode *Node) {
    if newNode.Value < currNode.Value {
        if currNode.Left == nil {
            currNode.Left = newNode
        } else {
            insertNode(currNode.Left, newNode)
        }
    }
    if newNode.Value > currNode.Value {
        if currNode.Right == nil {
            currNode.Right = newNode
        } else {
            insertNode(currNode.Right, newNode)
        }
    }
}

func (tree *Tree) ContainsValue(value int) bool {
    return getNode(tree.RootNode, value) != nil
}

func getNode(currNode *Node, value int) *Node {
    if currNode == nil {
        return nil
    }
    if currNode.Value == value {
        return currNode
    }
    if value < currNode.Value {
        return getNode(currNode.Left, value)
    }
    return getNode(currNode.Right, value)
}

```

One Pager Cheat Sheet