Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structures & Algorithms > Trees > Flashcards

Trees Flashcards

1
Q

What is a Tree?

A

A tree is collection of nodes that have a parent-child relationship

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Tree

What are sibling nodes?

A

Sibling nodes are nodes that have the same parent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is an external (leaf) node?

A

An external node is a node with 0 children

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is an internal node?

A

An internal node is a node that has 1 or more children

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

True or False

An ancestor node of n is any node on the path from n to the root node

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

True or false

A descendent node of n is any node on the path from n to a leaf node

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is an edge?

A

An edge is a pair of nodes such that one is a parent of the other. In different words, an edge is a link between 2 immediate nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What indicates if a tree is sorted?

A

If there is a meaningful linear order among the nodes at each level, the tree is sorted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q
  1. How can you calculate the depth of node n?
  2. What is the depth of a tree’s root node?
A
  1. The depth of node n is the number of edges from n to the root node
  2. Depth of root node = 0
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Binary Search Tree

What happens when you insert sorted data into a Binary Search Tree?

A

Inserting sorted data will casue a Binary Search Tree to become linear. For example, inserting 1, 2, 3 will cause the tree to look like:

1
 \
	2
	  \
		 3
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

True or false

For N nodes in an unbalanced tree, there are approximately log(N) levels

A

False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Describe how a Binary Search Tree works

A

A Binary Search Tree is a sorted tree where each parent has at most 2 children. The left child is less than the parent node and the right child is greater than the parent node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q
  1. How can you calculate the height of node n?
  2. What is the height of a tree?
A
  1. The height of node n is the number of edges from n to its deepest node
  2. The height of a tree is the number of edges from the root node to its deepest node
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How can you calculate the number of edges in a tree?

A

Number of nodes - 1 = total edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

True or False?

2^level = number of nodes at that level

A

True. For example:
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What 2 types of trees automatically rebalance themselves?

A
  1. Red Black Trees
  2. AVL Trees
17
Q

What is the traversal order of:

  1. In-order traversal
  2. Pre-order traversal
  3. Post-order traversal
A
  1. Left -> Root -> Right
  2. Root -> Left -> Right
  3. Left -> Right -> Root
18
Q

Why is the right not a Binary Search Tree?

A

Data Structures & Algorithms (13 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions