Binary Trees

Question 1

What is a tree?

Answer 1

A tree is a data structure consisting of nodes.

• Each tree has a root node
• Each root node has zero or more
• Each child node has zero or more nodes and so on.

Question 2

Balanced vs Unbalanced

Answer 2

Does not necessarily mean that the tree has the same exact number of leaves. It just needs to be balanced enough to get O(logN) for insert and find.

Two common types of balanced trees are AVL and red/black trees.

Question 3

Complete Binary Tree

Answer 3

Where every level is filled except the very last level. To the extent the last level is filled, its filled left to right.

Question 4

Full Binary Tree

Answer 4

When every node has two or zero children.

Question 5

Perfect Binary Trees

Answer 5

One that is full and complete. All leaves are the same level and have the maximum number of nodes.

Question 6

Traversal

Answer 6

In-order:
“Visiting” left, current, then right branch.

Pre-order:
“Visits” current before the children.

Post-order:
“Visits”

Question 7

Binary Heaps (Min/Max Heaps)

Answer 7

A min heap is a complete binary tree where each node is smaller than its children. It is totally filled other than the rightmost elements on the last level. The root is the minimum element of the tree.

There are two functions: insert and extract_min.
Insert:
We start by inserting the element at the bottom. We insert at the right most spot as to maintain “complete tree” property.
We fix the tree by swapping the parent with the child…essentially bubbling up the min value.

Extract_min:
Remove min is easy because its always at the top. We remove the element by swapping it with the last element in the heap. When choosing which child to use in any situation, choose the one with the lesser value.

Question 8

Trie (Prefix trees)

Answer 8

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

• (aka null nodes) represent complete words. the implementation might be a special type of child (like TerminatingTrieNode which inherits from Trie Node). We could just use a boolean flag instead.

A trie could have anywhere from 1 thru ALPHABET_SIZE + 1 children.

There are used to store the entire English language for quick prefix lookups. A hash cant even tell is a string is prefix of any valid words. Tries can. O(lenOfStr) time.