Trees

Question 1

Complete binary tree

Answer 1

All levels have are fully filled (each node has 2 children) except possibly last level . The last level is filled left to right.

Question 2

Full binary tree

Answer 2

Every node has either 0 or two children. No nodes have 1 child.

Question 3

Perfect binary tree

Answer 3

Both complete and full. All leaf nodes at same level. Last level has max number of nodes. Perfect trees rare in interviews and real life, just make sure to not assume a tree is perfect.

Question 4

4 Aspects of a tree:

Answer 4

1) root node (theoretically optional, but in the interview this is there)
2) root node has 0+ children nodes
3) children have 0+ children nodes
4) no cycles
(May or may not have order, any data type possible as values)

Question 5

Binary tree:

Answer 5

A tree where each node has up to 2 child nodes

Question 6

Binary SEARCH tree

Answer 6

A binary tree with a useful property: all left descendants <= n

Question 7

Balanced

Answer 7

Does not mean the left and right subtrees are exactly the same size. Just that they’re close enough for log(n) Insert and find. Not max balance!!!

Question 8

3 options for traversing binary search tree

Answer 8

Post order, pre order, in-order (see pg 103 of ctci for code of each way. Remember that!)

Question 9

Min heap

Answer 9

Complete binary tree where each node is smaller than its children. So the root is the minimum element. Max heap is the same just upside down basically

Question 10

Key operations on a min heap:

Answer 10

Insert O(log(n))

Extract_min 0(log(n))

Remember how to do these! Ctci 104

Question 11

Trie

Answer 11

Basically stores words in a tree. Can have anywhere from 0 to ALPHABETSIZE+1 children for any node. Used for quick prefix lookups

Question 12

Graph vs tree

Answer 12

More general than tree. A tree is a connected graph without cycles.

Question 13

Graph:

Answer 13

Collection of nodes with edges between some of them. Can be directed or undirected. Might consist of multiple isolated sub graphs.

Question 14

Ways to represent graphs

Answer 14

Adjacency list (most popular): 
Every node stores a list of adjacent      vertices. In undirected, an edge between 2 nodes is stored twice (in each notes adjacency list) 

Adjacency matrices: an NxN Boolean matrix where N is number of nodes. The value at a point indicates if there is an edge from node to node.

Question 15

Graph searches;

Answer 15

Bfs, dfs (see ctci and do practice problems with this)