# Trees Flashcards

1
Q

BFS

A

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

2
Q

complete binary tree

A

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

3
Q

full binary tree

A

every node has 2 or 0 children

4
Q

How do you find the shortest path?

A

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

5
Q

Depth First Search

A

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

6
Q

What are tree data structures optimized for?

A

Searching and sorting

7
Q

What is a degenerate tree?

A

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

8
Q

Binary Search Tree Insertion/Deletion Time Complexity

A

log n

9
Q

What is a Binary Search Tree?

A

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
10
Q

Binary Search Time Complexity

A

log n

array must be sorted
BST is sorted by definition

11
Q

Breadth First Search - Pros & Cons

A

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.
12
Q

DFS Preorder

A

Root - Left - Right

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

13
Q

DFS Inorder

A

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

14
Q

DFS Postorder

A

Left - Right - Root
Used to delete a tree