Trees intro Flashcards
1
Q
What r the general types of trees?
A
1 - family trees 2 - Decision trees 3 - expression trees 4 - file system 5 - hirearchy 6 - to express syntax in code
2
Q
why are trees important and there are so many of them?
A
1 - dynamic DS
2 - structure conveys information
3
Q
what is the recursive definition of a tree?
A
empty or :
with a node:
which have a key and might have child nodes
4
Q
what is the root?
A
the top node in a tree
5
Q
what is a leaf?
A
a node with no children
6
Q
what is an interior node?
A
a node with a child
7
Q
what is a level?
A
1+ the number of edges between root and node
8
Q
what is the height?
A
maximum depth of subtree node and farthest leaf
9
Q
what is a forest?
A
a collection of trees?
10
Q
what is BFS?
A
it’s breadth first search:
we check all the connections at on time
11
Q
what is DFS?
A
it’s depth first search:
we check only one connection at a time
12
Q
what is the DS for BFS?
A
queue
13
Q
what is the DS for DFS?
A
stack
