Trees

Question 1

BFS

Answer 1

uses queue to find shortest path
iterative soln while q
for cycle problems, use a set to keep track of visited nodes

Question 2

complete binary tree

Answer 2

all levels are completely filled in except for the last level which is filled from left to right

Question 3

full binary tree

Answer 3

every node has 2 or 0 children

Question 4

How do you find the shortest path?

Answer 4

Use BFS. (DFS is not guaranteed to find the shortest path.)

Question 5

Depth First Search

Answer 5

Uses a stack! Recursive.

Pros

Optimal for searching a tree that is deeper than it is wide

Generally requires less memory than BFS.

Cons

Doesn’t necessarily find the shortest path to a node

Question 6

What are tree data structures optimized for?

Answer 6

Searching and sorting

Question 7

What is a degenerate tree?

Answer 7

Every parent node has only one child. Can be treated like a linked list

Question 8

Binary Search Tree Insertion/Deletion Time Complexity

Answer 8

log n

Question 9

What is a Binary Search Tree?

Answer 9

For each node:

• The node’s value is greater than all values in the left subtree
• The node’s value is less than all values in the right subtree
• If the tree is balanced, searching for a given value takes log n time

Question 10

Binary Search Time Complexity

Answer 10

log n

array must be sorted
BST is sorted by definition

Question 11

Breadth First Search - Pros & Cons

Answer 11

Uses a queue! Iterative.

Pros:

• Will find the shortest path. DFS will not necessarily find the shortest path.
• Optimal for searching a tree that is wider than it is deep

Cons:

• Generally, requires more memory than DFS for binary trees because BFS travels farther each time it has to ascend than descend to a new level of the tree.

Question 12

DFS Preorder

Answer 12

Root - Left - Right

Used to copy a tree or when searching a binary search tree

Question 13

DFS Inorder

Answer 13

Left - Root - Right

root is in in the middle
left means left subtree, not left node
right means right subtree, not right node

in order traversal of a binary search tree gives you nodes in sorted order (that’s why it’s called in order)

the most common variant of dfs

Question 14

DFS Postorder

Answer 14

Left - Right - Root
Used to delete a tree

Question 15

Balanaced Tree

Answer 15

• also known as a height-balanced binary tree
• a binary tree where the height of the left and right subtrees of any node differ by no more than one
• height of a balanced tree is log n