# Trees Flashcards

BFS

uses queue to find shortest path

iterative soln while q

for cycle problems, use a set to keep track of visited nodes

complete binary tree

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

full binary tree

every node has 2 or 0 children

How do you find the shortest path?

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

Depth First Search

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

What are tree data structures optimized for?

Searching and sorting

What is a degenerate tree?

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

Binary Search Tree Insertion/Deletion Time Complexity

log n

What is a Binary Search Tree?

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

Binary Search Time Complexity

log n

array must be sorted

BST is sorted by definition

Breadth First Search - Pros & Cons

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.

DFS Preorder

Root - Left - Right

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

DFS Inorder

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

DFS Postorder

Left - Right - Root

Used to delete a tree