bst, trees, tries, graphs, bfs, dfs

Question 1

How do we find the left child of any parent element in a bst?

Answer 1

multiply the parent element’s index by 2 and add 1.

let left = 2indexOfParent + 1

Question 2

How do we find the right child of any parent element?

Answer 2

multiply the parent element’s index by 2 and add 2

let right = 2indexOfParent + 2

Question 3

What is the runtime of an unbalanced bst? What is the runtime of a balanced bst?

Answer 3

h = height of tree

unbalanced: O(h)
balanced: O(h)

Question 4

How do you calculate the height of a node in a bst?

Answer 4

max(heighRightCild, heightLeftChild) + 1

Question 5

What is the runtime of min(), max(), insert(), deletion() of a unbalanced bst? Balanced bst?

Answer 5

O(h)

h = length of longest path root to leaf
if balanced: h = O(lan)

Question 6

Implement breath first search in a binary search tree

Answer 6

bfs(root) {
let result = [];
let queue = [];

queue.push(root);

  while(queue.length) {
    let curr = queue.shift();
    result.push(curr.value)
    if (curr.left) {
      queue.push(curr.left)
    }
    if (curr.right) {
      queue.push(curr.right)
    }
  }

return result;
}

Question 7

What is a cycle?

Answer 7

When a path goes from a particular vertex back to itself

Question 8

What is a directed acyclic graph, or dag?

Answer 8

Directed graph with no cycles

Question 9

What is the in-degree?

Answer 9

The number of edges entering a vertex

Question 10

What is the out-degree?

Answer 10

The number of edges leaving a vertex

Question 11

What is a complete graph?

Answer 11

When all nodes are connected to all other nodes

Question 12

What is a connected graph?

Answer 12

If all nodes have at least one edge

Question 13

What is an Adjacency List?

Answer 13

A list of all the nodes connected to a node

Question 14

What are the 2 main ways graphs can be represented and what are the pros and cons of each

Answer 14

1. Adjacency lists
   - list of key value pairs
   - takes up less memory than matrix
   - not as easy to visualize
2. Adjacency matrix
   - 2d array filled with 1’s and 0’s
   - 1 means connection and 0 means no connection
   - takes up more space but easier to visualize and represent the data
   - example: if there are not a lot of edges then the matrix will be filled with lots of 0’s which are not used

Generally speaking, graphs with lots of edges fare better as matrices and graphs with fewer edges fare better as lists.

Question 15

How do you represent an ordered pair and how do you represent an unordered pair in mathmatics

Answer 15

order pair: (a,b) // order matters

unordered pair: {a,b} // order does not matter

Question 16

What what is a leaf?

Answer 16

node that does not have a child node in the tree

Question 17

What is the height of a tree?

Answer 17

the length of the longest path to a leaf

Question 18

What is the depth of a node?

Answer 18

the length of the path to its root

Question 19

What is a path?

Answer 19

Path refers to the sequence of nodes along the edges of a tree.

Question 20

What is the root node of a tree?

Answer 20

The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.

Question 21

Write an algorithm that checks if tree t is a subtree of tree s

Answer 21

public class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        if (isSame(s, t)) return true;
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }

private boolean isSame(TreeNode s, TreeNode t) {
    if (s == null && t == null) return true;
    if (s == null || t == null) return false;

    if (s.val != t.val) return false;

        return isSame(s.left, t.left) && isSame(s.right, t.right);
    }
}

Question 22

What type of traversal is good for shortest paths?

Answer 22

breath first search

Question 23

What type of traversal is good for solving mazes?

Answer 23

depth first search

Question 24

What is the runtime of breath first search?

Answer 24

O(n)

o(m+n) m = edges n = vertices (linear time)

Question 25

what is undirected connectivity

Answer 25

See if a vertex is included in a particular graph

Question 26

How do you find all connected components of an undirected graph given a list of node (all nodes are not necessarily connected to each other)? what is the runtime?

Answer 26

bfs strat
- given list of n nodes to check
- all nodes set to unexplored
- for i = a to n
  if i not yet explored do
  bfs(graph, i)
- in bfs we set each node's explored to true

runtime:
- look through all nodes -> m + n time -> n time
- O(1) timer per node in the bfs
O(n) runtime

Question 27

What is an arc in graph theory

Answer 27

a directed edge

Question 28

What it topological ordering?

Answer 28

it’s an ordering of the vertices of a graph so that all of the arcs, the directed edges of the graph, only go forward in the ordering.

a -> b -> c >d
a——–> c
b——–> d

• goes in one direction
• no cycle

Question 29

Minimal Tree: Given a sorted (increasing order) array with unique integer elements, write an
algorithm to create a binary search tree with minimal height

Answer 29

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

const createMinimalBST = (a) => {
  const midIndex = Math.floor(a.length / 2);
  const midElement = a[midIndex];
  const left = a.slice(0, midIndex);
  const right = a.slice(midIndex+1);

  const root = new Node(midElement);
  if(left.length) root.left = createMinimalBST(left);
  if(right.length) root.right = createMinimalBST(right);
  return root;
}