Trees & Graphs

Question 1

Binary Tree vs. Binary Search Tree

Answer 1

A binary search tree is a binary tree in which every node fits a specific ordering property: a l l l e f t descendents <= n < a l l r i g h t descendents. This must be true for each node n.

Question 2

Balanced vs. Unbalanced

Question 3

Complete Binary Trees

Answer 3

A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right,

Question 4

Full Binary Trees

Answer 4

A full binary tree is a binary tree in which every node has either zero or two children. That is, no nodes have only one child.

Question 5

Perfect Binary Trees

Answer 5

A perfect binary tree is one that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes.

Question 6

Binary Tree Traversal

Answer 6

InOrder (izquierda, raiz, derecha)
PreOrder (raiz, izquierda, derecha)
PostOrder (izquierda, derecha, raiz)

Question 7

Binary Heaps (Min-Heaps and Max-Heaps)

Question 8

Min-heap

Answer 8

A min-heap is a complete binary tree (that is, totally filled other than the rightmost elements on the last level) where each node is smaller than its children. The root, therefore, is the minimum element in the tree.

Question 9

Min-heap operations

Answer 9

insert
extract minimun element

Question 10

Tries (Prefix Trees)

Answer 10

A trie is a variant of an n-arytree in which characters are stored at each node. Each path down the tree may represent a word.

Question 11

Graphs

Question 12

Graph Search

Answer 12

Depth-First Search
Breadth-First Search

Question 13

Depth-First Search (DFS)

Answer 13

visit a node a and then iterate through each of a’s neighbors.

Question 14

Breadth-First Search (BFS)

Answer 14

visits each of a’s neighbors before visiting any of their neighbors.