binary trees

Question 1

what is a tree and why do we use it?

Answer 1

an example of a nonlinear data structure

used because some operations can be made more efficient

Question 2

define a binary tree

Answer 2

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

Question 3

preOrder traversal

Answer 3

root left right

node before it children

Question 4

postOrder

Answer 4

left right node

children before node - left most nodes are always visited first

Question 5

inOrder traversal

Answer 5

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

Question 6

level order traversal

Answer 6

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

Question 7

complexity analysis of bin trees

Answer 7

best = ave = worst

o(n)

Question 8

what are the level order space requirements

Answer 8

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