Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Cracking the Coding Interview > Ch 4: Trees and Graphs > Flashcards

Ch 4: Trees and Graphs Flashcards

1
Q

Trees:
Basic Types of Trees

A
  • Tree
  • N-ary Tree
  • Binary Tree
    • Binary Search Tree
      • Self Balancing Binary Search Tree
        • Red-Black Trees
        • AVL Trees
    • Binary Heaps
      • Min Heap
      • Max Heap
  • Tries (Prefix Trees)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Graphs:
Types of graphs and related data structures

A
  • Directed Graph
  • Undirected Graph
  • Cyclic Graph
  • Acyclic Graph

Data Structures:
* Adjacency List
* Adjacency Matrix

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Trees:
Tree Basic Description

A
  • A data structure composed of Nodes which can contain any data type as values
  • It is a type of Graph
  • Each tree has a Root Node
  • The Root Node has 0 or more Child Nodes
  • Each Child Node has 0 or more Child Nodes
  • Each Node may or may not have a pointer to it’s parent node
  • The tree cannot contain Cycles
  • Nodes may or may not be in a particular order
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Trees:
Leaf Node

A

A node in a tree that has no children

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Trees:
Root Node

A

The top-most node in a tree.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Trees:
Basic Tree Class Definition

A 
class Tree {

    class Node {
        public String name;
        public Node[] children;
    }
    
    public Node root;
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Trees:
Binary Tree basic description

A

A tree in which each node has up to 2 children

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Trees:
N-ary Tree basic description

A

A tree in which each node has up to N children

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Trees:
Binary Search Tree basic description

A

A Binary Tree in which every node fits a specific ordering property.
Some definitions allow duplicate values, some do not.
example:
For each node with value n,
All left descendants <= n
and
All right descendants > n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Trees:
Binary Tree Classifications

A
  • Balanced or Unbalanced
  • Completeness
  • Full
  • Perfect
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Trees:
Binary Tree Properties:
Balanced

A

A tree is balanced when the left and right subtrees are very close to the same size.
* Don’t have to be exactly the same size
* Should be close enough that insert and find operations are O(logn)
* Not necessarily as balanced as it could be

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Trees:
Common Types of Balanced Trees

A
  • Red-Black Trees
  • AVL Trees
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Trees:
Binary Tree Properties:
Completeness

A

A Binary Tree is Complete when:
* Every level of the tree is full, except the bottom
* Last level can be incomplete, but must be filled from left to right

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Trees:
Binary Tree Properties:
Fullness

A

A Binary Tree is Full when:
* Each Node has either 0 or 2 Children

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Trees:
Binary Tree Properties:
Perfect Binary Tree Properties

A

A Perfect Binary Tree
is both Complete, and Full.

This is rare, as it can only exist when the tree contains exactly
2^k - 1 nodes,
where k = number of levels in the tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Trees:
Binary Tree Traversal methods

A
  • In-Order Traversal
  • Pre-Order Traversal
  • Post-Order Traversal
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Trees:
Binary Tree
In-Order Traversal

A

Each node of the tree is visited recursively, from left to right

Visitation Order:
Left subtree -> Current Node -> Right Subtree

In a Binary Search Tree, where the nodes are organized in ascending order, the nodes are visited in ascending order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Trees:
Binary Tree
In-Order Traversal
pseudocode

A

void inOrderTraversal( TreeNode node) {
if (node != null) {
inOrderTraversal(node.left); // left child
visit(node); // current
inOrderTraversal(node.right); // right child
}
}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Trees:
Binary Tree
Pre-order Traversal

A

Each node of the tree is visited recursively
Current Node visited BEFORE it’s children.

Visitation Order:
Current Node -> Left Subtree -> Right Subtree

The Root Node is always the first node visited.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Trees:
Binary Tree
Pre-Order Traversal Pseudocode

A

void preOrderTraversal( TreeNode node) {
if (node != null) {
visit(node); // current
preOrderTraversal(node.left); // left child
preOrderTraversal(node.right); // right child
}
}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Trees:
Binary Tree
Post-Order Traversal

A

Each node is visited recursively,
Current Node is visited AFTER it’s children

Visitation Order:
Left Subtree -> Right Subtree -> Current Node

The Root Node is always the last node visited

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Trees:
Binary Tree
Post-Order Traversal Pseudocode

A

void postOrderTraversal( TreeNode node) {
if (node != null) {
postOrderTraversal(node.left); // left child
postOrderTraversal(node.right); // right child
visit(node); // current
}
}

23
Q

Trees:
Binary Heaps:
Min-Heap

A
  • A complete binary tree where each node is smaller than it’s children.
  • There is no inherent ordering between the two children, it depends on the order of insertion.
  • The root node is the minimum element in the tree
24
Q

Trees:
Binary Heaps:
Max-Heap

A
  • A complete binary tree where each node is larger than it’s children.
  • There is no inherent ordering between the two children, it depends on the order of insertion.
  • The root node is the maximum element in the tree.
25
Q

Trees:
Binary Heaps:
Key Operations

A
  • Insert
  • ExtractMin
    or
  • ExtractMax
26
Q

Trees:
Binary Heaps:
Insert Operation

A
  1. Insert new node at the bottom of the tree, in the rightmost position. This keeps the tree “complete”
  2. Move the node to it’s proper position by swapping it with it’s parent node until parent < current (Min Heap) or it is the root

Takes O(log n) time

27
Q

Trees:
Binary Heaps:
Extract Minimum(or Max) Element

A

In a Min Heap, the minimum element is always at the root.
The trick is removing it and retaining the correct order.

  1. Swap the root node with the last element in the heap (bottom, right-most node). Save the old root.
  2. Fix the tree by “bubbling down” the new root; swap it with whichever of it’s children is the smallest. It should end up near the bottom of the heap
  3. Return the old root

This takes O(log n) time

28
Q

Tries:
What is a Trie?

A
  • A variant of an n-ary tree in which characters are stored at each node.
  • Each node can have as many children as there are symbols in the alphabet being used
  • Each path down the tree represents a complete word or sequence
  • Uses either a “null node” or an internal flag in a regular node to indicate the end of a word
  • Also called a “Prefix Tree”
29
Q

Tries:
Uses of a Trie

A

Used to store entire languages for quick prefix lookups

Very useful for optimizing problems involving lists of “valid” words.

Can check if a word is valid in O(K) time, where K is the length of the string in question

30
Q

Tries:
Validating a word:
Hashtable vs Trie

A

A hashtable is able to store a dictionary of words and check if a word is valid, but it can’t tell if a string is a PREFIX of any valid words.

A hashtable will have a similar lookup time of O(K), where K is the length of the string.

31
Q

Graphs:
What is a graph?

A

A graph is a collection of nodes with connections(called edges) between some of them.

32
Q

Graphs:
Relationship between Trees and Graphs

A

A Tree is simply one type of graph:
A connected graph that does not contain cycles.

33
Q

Graphs:
Edges

A

Edges are the connections between nodes on a graph.
An edge can be:

  • Directed: one-way connection between nodes
  • Undirected: two-way connection between nodes
34
Q

Graphs:
Directed Graph

A

A graph in which all edges are directed (one way)

35
Q

Graphs:
Undirected Graph

A

A graph that contains undirected edges

36
Q

Graphs:
Connected Graph

A

A Graph where a path exists between every pair of vertices(nodes)

Ex: A Tree is a type of Connected graph.

37
Q

Graphs:
Cycle

A

A cycle is a set of nodes and edges where it is possible to revisit the same nodes over and over.

38
Q

Graphs:
Acyclic Graph

A

A Graph that does NOT contain any cycles

39
Q

Graphs:
Two common ways to represent graphs

A
  • Adjacency List
  • Adjacency Matrix
40
Q

Graphs:
Adjacency List

A

The most common way to represent a graph.
Every vertex(or node) stores a list of pointers to adjacent vertices.
- An undirected edge (a, b) would be stored twice: once in node a, once in node b

Can be implemented with a Graph class and a Node class,
or
Can be implemented with an array or hashtable of lists, each entry
storing an adjacency list for a single node.

Implementing with Node classes is typically preferred.

41
Q

Graphs:
Adjacency Matrix

A

An NxN boolean matrix (N = number of nodes)
(May also represent with integers instead of booleans)

  • A true value at matrix[ i ][ j ] indicates an edge from node i to node j
  • In an undirected graph, an adjacency matrix will be symmetric
    (matrix[ i ][ j] == matrix[ j ][ i ]
42
Q

Graphs:
Adjacency List
vs
Adjacency Matrix

A
  • The same graph algorithms used on adjacency lists (Breadth First Search, etc) CAN be performed with adjacency matrices, but may be less efficient.
  • An Adjacency List makes it easy to iterate through a node’s neighbors
  • To identify neighbors in an Adjacency Matrix, you must iterate through all the nodes
43
Q

Graph Search:
Two most common ways to search a graph

A
  • Depth-First Search (DFS)
  • Breadth-First Search (BFS)
44
Q

Graph Search:
Depth First Search (DFS)
Basic idea

A
  • Start at the “root” (or another arbitrarily selected node)
  • Explore each branch COMPLETELY before moving on to the next branch.
  • We go “deep” first, before we go “wide”
  • Often preferred when wanting to visit every node in the graph
  • A bit simpler than BFS
  • Easy to implement recursively
  • in a cyclic graph, must keep track of nodes visited to avoid getting stuck in a cycle
45
Q

Graph Search:
Breadth First Search
Basic Idea

A
  • Start at the “root” (or another arbitrary selected node)
  • Explore each neighbor before going on to any of their children
  • We go “wide” first, before we go “deep”
  • Generally better for finding the shortest path between two nodes
  • A bit more complicated than DFS
  • Is NOT recursive
  • Key Data Structure: Queue of nodes to visit
46
Q

Graph Search:
Depth First Search
vs
Breadth First Search

A

DFS:
* simpler
* often preferred when visiting all nodes

BFS:
* more complex
* better at finding a path between two nodes

47
Q

Graph Search:
Depth First Search

Pseudocode Steps

A

DepthFirstSearch(Node node){
if(node == null) return;

visit(node); 
node.visited = true;

for each( Node n in node.adjacent) {
    if(n.visited == false) DepthFirstSearch(n)
} }

DepthFirstSearch(root);

48
Q

Graph Search:
Depth First Search:
What is the visitation order of this graph:

A
49
Q

Graph Search:
Breadth First Search:
What is the visitation order of this graph?

A
50
Q

Graph Search:
Breadth First Search Pseudocode

A
51
Q

Graph Search:
Bidirectional Search

A
  • Used to find the shortest path between two nodes
  • Essentially, runs two simultaneous breadth-first searches, one from each node.
  • When the searches collide, we have found a path
52
Q

Graph Search:
Bidirectional Search compared to
Breadth First Search

A

Consider a graph where every node has 0 to k adjacent nodes
* the shortest path from node s to node t has a length of d

BFS:
* Search up to k nodes in first “level” of the search
* Search up to k^2 nodes in second level
* takes O(k^d) time to reach a path of length d

Bidirectional Search:
* Two searches collide after about d/2 “levels” ( at the midpoint of the path)
* Takes O(k^d/2) for each search, or O(2k^d/2)

Bidirectional Search is faster by a factor of k^d/2

53
Q

Trees and Graphs:
Additional Topics related to this chapter

A
  • Topological Sort
  • Dijkstra’s Algorithm
  • AVL Trees
  • Red-Black Trees

Cracking the Coding Interview (10 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions