Brainscape's Knowledge GenomeTM

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


See full index

Hector > Trees > Flashcards

Trees Flashcards

1
Q

What is a Node?

A
  • The elements of the tree
  • Each node contains a key which uniquely identifies that node
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is an Edge?

A

The link/connection between nodes

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

What is unique about the root node?

A

It has no parent

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

What are leaf nodes?

A

Nodes that have no child

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

What is a Path?

A

A sequence of nodes connected by edges

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

How is the length of a path determined?

A

Determined by the number of nodes in the path (including start and end nodes)

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

What is a Parent node?

A

The unique predecessor of every node

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

What is a Child node?

A

The successor to a parent node

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

What are Sibling nodes?

A

Nodes that have a common parent

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

What is the Level of a node?

A
  • The number of nodes between this node and the root node
  • Calculated using the shortest path to the root node
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the height of a tree?

A

The height is determined by the highest level node

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

What are Sub-trees?

A
  • A Sub-tree is formed using a parent node and all of it’s descendants.
  • The parent node becomes the root node of the Sub-tree.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the difference between a Strictly Binary Tree and a Knuth Binary tree?

A
  • Each node in a Strictly Binary tree has either 0 or 2 sub-trees
  • Each node in a Knuth Binary Tree can have 0, 1 or 2 sub trees
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What 3 qualities make Trees a recursive data structure?

A
  1. The data of the node itself
  2. A reference to the left child node (can be null)
  3. A reference to the right child node (can be null)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What makes a tree balanced?

A

All leaf nodes have the same level

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

What is a Breadth-first traversal?

A

Returns the data of each node level by level

(e.g. returns all nodes at level 1, then level 2, etc.)

17
Q

What is the procedure for a Depth first Pre-order traversal?

A
  1. Process current node
  2. Traverse to left sub-tree
  3. Return to parent node
  4. Traverse to right sub-tree
  5. Return to parent node

-Process, Left, Right or P, L, R

18
Q

What is the procedure for a Depth first In-order traversal?

A
  1. Visit current node
  2. Traverse to left sub-tree
  3. Process current node
  4. Traverse to right sub-tree
  5. Return to parent node
  • Left, Process, Right or LPR
19
Q

What is the procedure for a Depth first Post-order traversal?

A
  1. Visit current node
  2. Traverse to left sub-tree
  3. Visit current node
  4. Traverse to right sub-tree
  5. Process current node
  6. Return to parent node
  • Left, Right, Process or LRP
20
Q

What is a Binary Search Tree (BST)?

A
  • A Binary Tree that is ordered so that, starting at the root, when we search for a node we always know which sub tree to search in
  • This mean the maximum number of comparisons = height of tree
21
Q

How is a BST organised?

A
  • The values in the left sub-tree are always less than the parent

-The values in the right sub-tree are always greater than the parent

22
Q

What is the worst-case and best-case time complexity of searching a BST?

A
  • Worst case: O (n) when every parent node only has one child
  • Best case: O (log n) when every parent node has 2 children
23
Q

What type of traversal is needed to return an ordered list of items from a BST?

A

Depth first in-order traversal

24
Q

What is a Full Binary tree?

A

A binary tree where every level of the tree has the maximum possible number of nodes

25
Q

What is a B-Tree?
(not a binary tree)

A

A tree where nodes contain multiple key values, and have multiple children

26
Q

What are the benefits of a B-Tree?

A
  • Can be efficiently stored in files and memory
  • Minimise disk reads ( complexity of O (log n)
27
Q

What are the applications of a B-Tree?

A
  • Suitable for datasets that are too large to fit in main memory
  • Useful for databases and file systems
28
Q

What are the limitations of a B-Tree?

A
  • Often half empty (inefficient use of space)
  • Sequential access requires revisiting nodes
29
Q

What is the degree/order of a B-Tree?

A

The order (M) of a B-Tree is the maximum number of children allowed per parent

30
Q

How many children does each node of a B-Tree have?

A

Between M and M/2 with M being the order of a B-Tree

31
Q

How many key values do parents have in a B-Tree?

A
  • Number of children -1
  • So for a parent with 4 children, it would have 3 key values
32
Q

Describe the Node splitting method

A
  1. When a node is full (M elements), split into two nodes at the same level as the original node
  2. Put the smallest elements into the left node
  3. Put the largest elements into the right node
  4. Insert the middle element into the parent node
  5. If no parent node exists, create a new root node and insert the middle element
33
Q

How do you convert this infix expression:
(A + B) * C - D / E
into a prefix expression?

A
  1. (A + B) = AB+
  2. (A + B) * C = AB+C*
  3. D / E = DE/

AB+C*DE/-

34
Q

Why are expressions converted into prefix forms?

A
  • Can be processed with a single left to right pass
  • Easier to build an expression tree
35
Q

How are expression trees formatted?

A
  • Parent node will be the operator
  • Child nodes will be the two elements being processed

e.g. the parent node could be + and the child nodes would be the element A, and the subtree B*C (will be processed recursively)

36
Q

How is a modified in-order traversal used to evaluate an expression tree?

A
  1. IF parent node, then print (
  2. Left
  3. Process
  4. Right
  5. IF parent node, print )
37
Q

How is a post order traversal used to evaluate an expression tree?

A
  • Left, Right, Process
  • Using a stack data structure means we don’t need parentheses
    e.g. ABCD-+ will return:
    C-D, B    (C-D), A+B*(C-D)

Hector (17 decks)

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