Data Structures: Trees

A "tree-like", derived, Data Structure that has zero or more child instances, each instance taking a value:

Trees are a kind of Graph which has a Root node.
Each parent node has one or more child nodes.

Attributes

Value
children - empty or other Tree Node instances.

Implementations

var TreeNode = function(val, children = []) {
    this.val = val;
    this.children = children;
}

Search

Depth First Search - refer to the Search article.
- Top to Bottom, Left to Right
- By Column
Breadth First Search - consult the Level Recursion article.
- Left to Right, Top, to Bottom
- By Row or Level
N-Trees vs BST
- For N-Trees replace Left and Right child nodes with Children List or Array.

Notes

A LinkedList can be thought of as Tree with only one child element at each node.

Resources and Links

Code samples:

https://github.com/Thoughtscript/cplusplus-coursera/tree/master/course/11%20-%20Generic%20Tree

Data Structures: Binary Trees

A "tree-like", derived, Data Structure that connects left and right child instances, each instance taking a value.

Useful resource: https://trees-visualizer.netlify.app/trees

Binary Trees

A Tree with at most two children.
Ordered by constraints.
- Binary Heap
  - A Binary Tree
  - Max: the value of any child of a parent node is greater than or equal to the parent.
  - Min: the value of any child of a parent node is less than or equal to the parent.
  - Average Read: O(n)
  - Average Add: O(1)
- Binary Search
  - A Binary Tree
  - The value of the left child node of a parent node must be less than or equal to the value of the parent node.
    - L <= P
  - The value of the right child node of a parent node must be greater than or equal to the value of the parent node.
    - R >= P
  - Therefore, any value of any right node of the root node will be greater than the value of any left node.
  - Therefore, any value of any left node of the root node will be less than the value of any right node.
  - Average Read: O(log(n))
  - Average Add: O(log(n))
- AVL Tree (Georgy Adelson-Velsky and Evgenii Landis)
  - A Self Balancing Binary Search Tree (dynamic)
  - Heights of each branch differ by at most 1.
  - A self-balancing algorithm executes if heights differ by more than 1.
Perfect
- Balanced and all leaves are at the same depth.
- Each branch is complete, has two children, and is at the same height as the rest.
Balanced
- Each branch differs in height no more than one compared to any other in the tree.
Complete
- Each node except the last is completely filled (has two children).
- Each node in the last row is as far left as possible.

Attributes

Value
left - null, nil, or none or another Binary Tree Node instance.
right - null, nil, or none or another Binary Tree Node instance.

Implementations

var TreeNode = function(val, left, right) {
    this.val = val;
    this.left = left;
    this.right = right;
}

Depth First Search

Pre Order - current node first, left node, then right node last
In Order - left node first, then current node, then right node last
Post Order - left node first, right node second, then current node last

const preOrder = node => 
{
  const traverse = (node, result) => {
    if (!node) result.push(null)
    else {
      result.push(node.data)
      if (node.left) traverse(node.left, result)
      if (node.right) traverse(node.right, result)
    }
  }
  let result = []
  if (!node) return result
  traverse(node, result)
  return result
}

const inOrder = node => 
{
  const traverse = (node, result) => {
    if (node.left) traverse(node.left, result)
    result.push(node.data)
    if (node.right) traverse(node.right, result)
  }
  let result = []
  if (!node) return result
  traverse(node, result)
  return result
}

const postOrder = node => 
{
  const traverse = (node, result) => {
    if (!node) {}
    else {
      if (node.left) traverse(node.left, result)
      if (node.right) traverse(node.right, result)
      result.push(node.data)
    }
  }
  let result = []
  if (!node) return result
  traverse(node, result)
  return result
}

Refer to: https://www.codewars.com/kata/5268956c10342831a8000135

Breadth First Search

Level Recursion - Traverse by each level of a Binary Search Tree

def tree_by_levels(node):
    result = []
    
    if node is None:
        return result
    
    level = [node]
    nxt = []
    
    while len(level) > 0:
        temp = []
        count = 0
        l = len(level)
        
        while count < l:
            if (len(level) > 0):
                c = level.pop(0)
                if c is None:
                    continue
                temp.append(c.value)
                nxt.append(c.left)
                nxt.append(c.right)
            count += 1
        
        if len(temp) > 0:
            for x in range(0, len(temp)):
                result.append(temp[x])
        level = nxt

    return result

Refer to: https://www.codewars.com/kata/52bef5e3588c56132c0003bc

Make a Balanced Binary Search Tree

Given a sorted Array or List:

const sortedArrayToBST = A => {
    const L = A.length
    if (L === 0) return null
    if (L === 1) return new TreeNode(A[0], null, null)
    if (L === 2) return new TreeNode(A[1], new TreeNode(A[0], null, null), null)
    if (L === 3) return new TreeNode(A[1], new TreeNode(A[0], null, null), new TreeNode(A[2], null, null))
    if (L > 3) return recurse(A)
}

const findPivot = arr => arr[Math.floor(arr.length / 2)]

const firstHalf = arr => arr.slice(0, Math.floor(arr.length / 2))

const secondHalf = arr => arr.slice(Math.floor(arr.length / 2) + 1, arr.length)

const recurse = A => {
    const L = A.length
    
    if (L === 0) return null
    if (L === 1) return new TreeNode(A[0], null, null)
    if (L === 2) return new TreeNode(A[1], new TreeNode(A[0], null, null), null)
    if (L === 3) return new TreeNode(A[1], new TreeNode(A[0], null, null), new TreeNode(A[2], null, null))
    if (L > 3) {
        let node = new TreeNode(findPivot(A), null, null)
        node.left = recurse(firstHalf(A))
        node.right = recurse(secondHalf(A))
        return node
    }
}

Resources and Links

Code samples:

Data Structures: Singly Linked List

A "chain-like", derived, Data Structure that connects instances head to tail through a next attribute, each instance taking a value.

Attributes

Value
Next - null, nil, none, or another Linked List instance.

Time Complexity

Generally, the average time complexity for most operations will be O(N). One needs to traverse through a Linked List to find the right instances to alter, insert a new instance between, remove, etc.

Average Read: O(N)
Average Add: O(N)

The best case is O(1) - the desired instance can be right at the beginning of the Linked List at the head.

Implementations

// JavaScript
var LinkedList = function(val, next) {
    this.val = val;

    if (next === undefined || next === null) this.next = null;
    else this.next = next;
}

Here, I implement a very simple Linked List. Java's default LinkedList tracks head and tail via index. The implementation below explicitly stipulates a head and tail and uses Node objects (specifically the next property) to create a chain.

// Java
public class Node {
  private Node next;
  private Object data;

  public Node(Object data, Node next) {
    this.data = data;
    this.next = next;
  }

  //... Getters and Setters
}

public class LinkedList {
  private Node head;
  private Node tail;

  public LinkedList() {
    Node tail = new Node(null, null);
    this.head = new Node(null, tail);
    this.tail = tail;
  }

  public LinkedList(Node head, Node tail) {
    this.head = head;
    this.tail = tail;
  }
}

Common Operations

// JavaScript
function append(head, val) {
  if (head == null) head = new LinkedList(val, null);
  else {
    var current = head;
    while (current.next != null) {
      current = current.next;
    }
    current.next = new LinkedList(val, null);
  }
  return head;
};

function prepend(head, val) {
  if (head == null) head = new LinkedList(val, null);
  else {
    var current = head;
    head = new LinkedList(val, current);
  }
  return head;
};

/** Remove by value not by index. */
function del(head, val) {
  let current = head, arr = []
    
  while (current != null) {
    if (current.val != val) arr.push(current.val)
    current = current.next
  }
  
  return buildList(arr);
};

/** - Starting At 1 */
function insrt(head, val, position) {
  if (head == null) head = new LinkedList(val, null);
  else {
    var current = head;
    var last = head;
    for (var i = 1; i < position; i++) {
      last = current;
      current = current.next;
    }
    current = new LinkedList(val, current);
    last.next = current;
  }
  return head;
};

function checkCycle(head) {
  if (head == null) return false;
  else {
    var alreadyIn = [];
    var current = head;
    while (current != null) {
      if (alreadyIn.indexOf(current.val) == -1) alreadyIn.push(current.val);
      else return true;
      current = current.next;
    }
    return false;
  }
};

Notes

A LinkedList can be thought of as Tree with only one child element at each node.

Resources and Links

Data Structures: Stack

A "paper-stack" like derived object that's LIFO (last in, first out).

Often implemented with an Array or LinkedList.

Fun Algorithms

Stacks are often useful when two potentially non-contiguous items must be paired and/or canceled out (such as (, ) pairs).
In such cases, items can be added to a Stack (push), compared against the top of the Stack (peek), and removed (pop).

Consider Reverse Polish Logic Notation:

// Assumptions/Constraints: WFF, whitespaces correctly spaced
String[] A = "T T → T → T →".split(" ");

Stack<String> S = new Stack<>();

for (int i = 0; i < A.length; i++){
    String P = A[i];

    if (P.equals("∨")) {
        String X = S.pop();
        String Y = S.pop();
        if (X.equals("T") || Y.equals("T")) S.push("T");
        else S.push("F");

    } else if (P.equals("∧")) {
        String X = S.pop();
        String Y = S.pop();
        if (X.equals("T") && Y.equals("T")) S.push("T");
        else S.push("F");

    } else if (P.equals("→")) {
        String X = S.pop();
        String Y = S.pop();
        if (X.equals("T") && Y.equals("F")) S.push("F");
        else S.push("T");

    } else if (P.equals("¬")) {
        String X = S.pop();
        if (X.equals("T")) S.push("F");
        else S.push("T");

    } else S.push(P);
}

//S.pop()

T T → T → T → is equivalent to ((T → T) → T) → T in standard notation. The key insight here is that every operator is surrounded by a pair of Booleans.

Consider Reverse Polish Notation:

// Assumptions/Constraints: WFF, whitespaces correctly spaced
String[] A = "2 2 + 2 1 + * 2 +".split(" ");

Stack<String> S = new Stack<>();

for (int i = 0; i < A.length; i++){
    String X = A[i];

    if (X.equals("+")) S.push(S.pop() + S.pop());

    else if (X.equals("-")) {
        Double N = S.pop();
        Double M = S.pop();
        S.push(M - N);

    } else if (X.equals("/")) {
        Double N = S.pop();
        Double M = S.pop();
        S.push(M / N);

    } else if (X.equals("*")) S.push(S.pop() * S.pop());

    else S.push(Double.parseDouble(X));
}

//S.pop()

2 2 + 2 1 + * 2 + is equivalent to ((2 + 2) * (2 + 1)) + 2 in standard notation. The key insight here is every that every operator is surrounded by a pair of Numbers.

Also, Valid Parentheses:

String input = "({{{}[][][][][][][]}}()[])";

Stack<String> S = new Stack<>();

for (int i = 0; i < input.length(); i++){
    String P = String.valueOf(input.charAt(i));

    if (P.equals(")")) {
        if (S.size() > 0 && S.peek().equals("(")) S.pop();
        else S.push(P);

    } else if (P.equals("}")) {
        if (S.size() > 0 && S.peek().equals("{")) S.pop();
         else S.push(P);

    } else if (P.equals("]")) {
        if (S.size() > 0 && S.peek().equals("[")) S.pop();
        else S.push(P);

    } else S.push(P);
}

//S.pop()

Every pair of Parentheses must pair and cancel each other out.

A Stack variant of Math Equation Solver (eval or the like not allowed):

// Assumptions/Constraints: WFF, parentheses valid
String inputString = "((((12/3)/2)-(-5*4))+10)";

Stack<Character> P_stack = new Stack<>();
Stack<Double> N_stack = new Stack<>();
Stack<Character> O_stack = new Stack<>();
String currentNum = "";

for (int i = 0; i < inputString.length(); i++) {
    Character C = inputString.charAt(i);

    if (C.equals(left)) P_stack.push(C);

    else if (C.equals(right)) {
        if (currentNum.length() > 0) {
            N_stack.push(Double.valueOf(currentNum));
            currentNum = "";
        }

        if (P_stack.peek().equals(left)) {
            P_stack.pop();

            if (N_stack.size() > 1) {
                Double X = N_stack.pop();
                Double Y = N_stack.pop();
                Character O = O_stack.pop();

                if (O.equals(add)) N_stack.push(X + Y);
                if (O.equals(multi)) N_stack.push(X * Y);
                if (O.equals(div)) N_stack.push(Y / X);
                if (O.equals(sub)) N_stack.push(Y - X);
            }
        }
    }

    else if (C.equals(add) || C.equals(sub) || C.equals(multi) || C.equals(div)) {
        if (C.equals(sub)) {
            Character L = inputString.charAt(i-1); // Will never be first number with correct parentheticals
            if (L.equals(add) || L.equals(sub) || L.equals(multi) || L.equals(div) || L.equals(left)) currentNum += "-";
            else {
                O_stack.push(C);

                if (currentNum.length() > 0) {
                    N_stack.push(Double.valueOf(currentNum));
                    currentNum = "";
                }
            }

        } else {
            O_stack.push(C);

            if (currentNum.length() > 0) {
                N_stack.push(Double.valueOf(currentNum));
                currentNum = "";
            }
        }
    }

    else currentNum += C;
}

//N_stack.pop()

Same intuitions as before but using alternating Stacks.

Resources and Links

Code samples:

Data Structures: Queue

A "waiting line" (British "queue") and derived object that's FIFO (first in, first out).

Often implemented with an Array or LinkedList.

Resources and Links

Code samples:

https://www.codewars.com/kata/52a64cf14009fd59c6000994 <- using implicit ordering of JS keys for Priority Queue
https://leetcode.com/problems/implement-stack-using-queues/ <- top answer
https://github.com/Thoughtscript/java_algos/blob/main/src/main/java/io/thoughtscript/algos/gfg/queues/MinimumTotalCostReducingToOneElement.java

Data Structures: Sets

Most languages provide some implementation (or approximation) of the (the Pure Mathematics) Set Theoretic conception.

In Pure Mathematics, Sets are defined by the following:

As mathematical objects that "contain" other such objects (typically, in the manner specified by the axioms of ZFC Set Theory) - when they are allowed to "contain" themselves (Impredicativity) it leads to the notorious Cantorian Paradoxes (e.g. - Naive Set Theory).
They are denoted by pairs of enclosing curly braces: {, }.
∈ stands for the elemental inclusion operator and A ∈ B is read as Set A is an element of Set B (e.g. - B := { A, ... })
Where the order and duplication of elements are irrelevant and aren't preserved.
Where the identity of two Sets is determined by them having the exactly same elements.
Where the Null Set is always an element of every Set.
Where various common operations like Union, Complementation, Proper Subset, Intersection, and the like are defined using the above definitions.

Programmatically, Sets are generally characterized by the following (slightly weaker) constraints:

The order of their elements isn't preserved.
Their elements are deduplicated.
Set Theoretic Identity and constraints on Impredicativity are respected.

Refer to: Algorithmic Implementations of Common Set Operations

There are some important differences between the above and the pure math conception:

In Set Theory (as a discipline of Mathematics), the Null Set is an element of every Set. This is usually ignored in most languages.
In plain Java, probably the closest native operation to Set Theoretic Intersection in the Collections API is retainAll(). retainAll() however modifies the first Set and Set Theoretic Intersection is a distinct Set. As such retainAll() is not precisely Set Theoretic Intersection.

Note that Apache's Java Common Collection Utils supplies both a customized retainAll() and intersection() methods that return distinct Sets.

Resources and Links

Data Structures: Useful

Some interesting Data Structures of note (that are typically variants of the above):

Priority Queue - a Queue that sorts elements by some specified Comparison or Priority.
- Define a Comparator to sort elements.
- Exposes Queue functionalities: add() - Heap Sorted, and in O(logN) time, contains(), peek() - returns first element without removing it, poll() - removes and returns first element, etc.
- Much faster than either (a) scratch bulding a Data Structure that's required to both store and sort each element or to (b) naively sort some existing Data Structure on each pass through a loop.
- Remember that PriorityQueue doesn't keep all elements in its Heap sorted.
- Instead, use poll() like so to extra the elements in successive order:
```
// Function to merge k sorted arrays.
public static ArrayList<Integer> mergeKArrays(int[][] arr, int K) {
  Queue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a));
      
  // O(K)
  for (int i = 0; i < K; i++) {
    // O(K)
    for (int j = 0; j < K; j++) {
        // O(log(K))
        pq.add(arr[i][j]);
    }
  }

  ArrayList<Integer> result = new ArrayList<>();
  while (pq.size() > 0) {
    result.add(pq.poll());
  }

  return result;
}
```
  https://www.geeksforgeeks.org/problems/merge-k-sorted-arrays/1
Tree Map - a Map that supports sorted Key Value pairs.
- Define a Comparator to sort elements.
- Exposes Map functionalities: put() - Heap Sorted, and in O(logN) time, containsKey(), get(), keySet(), etc.

Tries and Prefix Trees.

Often used to store Strings, words efficiently.
Enables efficient individual character by character spellchecking or autocompletion.

https://leetcode.com/problems/implement-trie-prefix-tree/

Simple Trie for sorted lexicons:

function buildTrie(...words) {
  words.sort()
  let trie = {}

  // evaluate each word
  for (let i = 0; i < words.length; i++) {
    const W = words[i]
  
    let current = trie
  
    // Simplified trie - no isWord
    for (let j = 0; j < W.length; j++) {
      const K = W.substring(0, j+1)
      if (!current[K]) current[K] = {}        
      if (j === W.length - 1) current[K] = null
      current = current[K]
    }  
  }

  return trie
}

https://www.codewars.com/kata/5b65c47cbedf7b69ab00066e/solutions/javascript

Study Guide 2023+

datastructures

Data Structures: Trees

Attributes

Implementations

Search

Notes

Resources and Links

Data Structures: Binary Trees

Binary Trees

Attributes

Implementations

Depth First Search

Breadth First Search

Make a Balanced Binary Search Tree

Resources and Links

Data Structures: Singly Linked List

Attributes

Time Complexity

Implementations

Common Operations

Notes

Resources and Links

Data Structures: Stack

Fun Algorithms

Resources and Links

Data Structures: Queue

Resources and Links

Data Structures: Sets

Resources and Links

Data Structures: Useful

Resources and Links