Trees and Graphs

Question 1

Trees

Answer 1

Data structures with a root node and children nodes. Each child may also have children. The tree does not contain cycles.

Question 2

Binary Trees

Answer 2

A tree in which each node has up to two children

Question 3

Leaf Node

Answer 3

A node with no children.

Question 4

Binary Search Tree

Answer 4

A binary tree in which every node fits a specific ordering property: left descendants <= n < all right descendants. This must be true for each node n and all of node n’s descendants, not just immediate children. Some binary search trees cannot have duplicates, others will have duplicates on the right, or either side.

Question 5

Balanced Tree

Answer 5

Balanced enough to ensure O(log n) for insert and find, but not necessarily perfectly balanced.

Question 6

Complete Binary Tree

Answer 6

A binary tree in which every level of the tree is completely filled, except for maybe the last level. Filling on the last level is from left to right.

Question 7

Full Binary Tree

Answer 7

A binary tree in which every node has either zero or two children. No nodes have only one child.

Question 8

Perfect Binary Tree

Answer 8

All Interior node have two children and all leaf nodes are at the same level.

Question 9

Number of Nodes in a Perfect Binary Tree

Answer 9

The first level has 20, the second level has 21, the ith level has 2(i-1) and the last level has 2(N-1) where N is the depth of the tree. Total: 2**N - 1.

Question 10

In-Order Binary Tree Traversal

Answer 10

Visit the left branch, then the current node, and finally, the right branch. When performed on a binary search tree, it visits the nodes in ascending order.

Question 11

Implement In-Order Binary Tree Traversal

Answer 11

If node is not null, traverse the left child, then visit the center node, and then traverse the right child.

Question 12

Pre-Order Binary Tree Traversal

Answer 12

Visits the current node before its child nodes. The root is always the first node visited.

Question 13

Implement Pre-Order Binary Tree Traversal

Answer 13

if node is not null, visit the current node, traverse the left child node, then traverse the right child node.

Question 14

Post-Order Tree Traversal

Answer 14

Visits the current node after its child nodes. The root is always the last node visited.

Question 15

Implement Post-Order Tree Traversal

Answer 15

if node is not null, traverse the left child node, then traverse the right child node, then visit the current node.

Question 16

Min-Heaps

Answer 16

Complete binary tree where each node is smaller than its children. The root is the minimum element of the tree. Two key operators exist: insert and extract_min

Question 17

Max-Heaps

Answer 17

Same as a min-heap, but elements are in descending order.

Question 18

insert

Answer 18

start by inserting the element at the bottom of the min-heap. Insert at the next available spot, so as to maintain the complete tree property. Then fix tree by swapping the new element with its parent, until we find an appropriate spot for the element. Bubble up mini element. This takes O(log n).

Question 19

Extract Minimum Element (Min Heap, Binary Search Tree)

Answer 19

Remove the min element and swap it with the last element in the heap. Then, bubble down element, swapping it with its smaller child until the min-heap property is restored. The algorithm will take O(log n) time.

Question 20

Tries (Prefix Trees)

Answer 20

Variant of an n-ary tree in which characters are stored at each node. Null or * words indicate the end (like the end of a word). Very commonly used to store the entire language for quick prefix lookups.

Question 21

Graphs

Answer 21

A collection of nodes connected by edges. Graphs can either be directed or undirected. Graphs may contain more than one disconnected sub-graphs.

Question 22

Connected Graph

Answer 22

A path exists between every pair of vertices of a graph.

Question 23

Acyclic Graph

Answer 23

Contains no cycles.

Question 24

Adjacency List

Answer 24

Every vertex or nodes stores a list of adjacent vertices. An undirected node will store each edge twice.

Question 25

Implement Adjacency List

Answer 25

One Graph Class with field nodes. One Node class with field children and field data.

Question 26

Adjacency Matrices

Answer 26

An NxN boolean matrix where N is the number of nodes in the graph. A true value at matrix[i][j] means edge from node i to node j. Undirected graphs have symmetric matrices.

Question 27

Depth-First Search

Answer 27

Start at root node or arbitrarily selected node, and explore each branch completely. DFS is preferred if we want to visit every node in the graph. Tree traversal algorithms are simpler forms of DFS, but w/o markers.

Question 28

Breadth-First Search

Answer 28

Start at root node or arbitrarily selected node, and explore each neighbor before moving onto any of their children. BFS is preferred if we want to find the shortest path between two nodes.

Question 29

Implement DFS

Answer 29

Recursive function searching a root node. If root node is null, return. Visit root, then mark it as visited. For each neighboring node, if node is not visited, search it recursively.

Question 30

Implement BFS

Answer 30

Use a method that searches the root node using a queue. Set root to marked. Enqueue the root. While queue is not empty, dequeue a node, visit the node. For all adjacent nodes, if the adjacent node is not marked, set it to mark, and enqueue the adjacent node.

Question 31

Bidirectional Search

Answer 31

Finds shortest path between a source and destination node. Two BFS run simultaneously from each node.

Question 32

Run time of BS vs. BFS

Answer 32

BS will have O(kd/2) while BFS will have O(kd) if we assume each node has at most k connections. This is because searching each level will require k*number of nodes we are searching. Previous levels will have at most k nodes.