binary trees Flashcards

1
Q

what is a tree and why do we use it?

A

an example of a nonlinear data structure

used because some operations can be made more efficient

2
Q

define a binary tree

A
• set of nodes and directed edges
• single root node
• exactly one incoming line and zero or more outgoing links
• no cycles
3
Q

preOrder traversal

A

root left right

node before it children

4
Q

postOrder

A

left right node

children before node - left most nodes are always visited first

5
Q

inOrder traversal

A

visit the node after the left child but before the right child
left node right
you will end up with a sorted list

6
Q

level order traversal

A

cannot be done as easily using a short recursive formula
use an auxilary queue data structure
- add root node to a queue
- while the queue is not empty - pop a node and visit it add its children to the queue

7
Q

complexity analysis of bin trees

A

best = ave = worst

o(n)

8
Q

what are the level order space requirements

A

equal to the number of children in the last level of the tree +- n/2