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
