DSA > Trees > Flashcards

Trees Flashcards

(60 cards)

Study These Flashcards
1
Q

A tree is defined as a ______.
A. Directed graph
B. Connected acyclic graph
C. Balanced graph
D. Weighted acyclic graph

A

B. Connected acyclic graph

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

In a rooted tree, the number of children a node has is its ____.
A. Height
B. Level
C. Degree
D. Depth

A

C. Degree

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

Which traversal visits nodes in the order: Left, Visit, Right?
A. Preorder
B. Inorder
C. Postorder
D. Breadth-first

A

B. Inorder

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

All internal nodes have exactly two children in a ______ binary tree.
A. Complete
B. Perfect
C. Full
D. Balanced

A

C. Full

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

Which operation moves a newly inserted heap element upward?
A. bubbleDown
B. heapifyDown
C. heapifyUp
D. rotateRight

A

C. heapifyUp

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

The height of a tree is defined as:
A. Maximum depth of any node
B. Number of children of the root
C. Distance between two siblings
D. Depth of the root

A

A. Maximum depth of any node

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

In a complete binary tree, nodes at the last level are filled from ______.
A. Right to left
B. Random order
C. Center outward
D. Left to right

A

D. Left to right

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

In a BST, where is the smallest element located?
A. Rightmost node
B. Leftmost node
C. Root always
D. Any leaf

A

B. Leftmost node

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

An AVL tree maintains balance if the height difference between left and right subtree is at most:
A. 0
B. 1
C. 2
D. 3

A

B. 1

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

Deleting a BST node with two children requires replacing it with:
A. Any leaf
B. In-order successor or predecessor
C. The root
D. Its sibling

A

B. In-order successor or predecessor

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

A max-heap must always satisfy the:
A. Height rule only
B. Structural property only
C. Heap-order property only
D. Structural AND heap-order property

A

D. Structural AND heap-order property

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

Which set representation uses a sequence of bits to indicate membership?
A. Hashing
B. Bit-string
C. Linked list
D. Tree set

A

B. Bit-string

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

The path between any two nodes in a tree is always ______.

A

unique

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

A tree with no nodes is called an ______ tree.

A

empty

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

The number of edges in a tree with n nodes is ______.

A

⌊i / 2⌋

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

In the array representation of a binary heap, the parent of node at index i is at index ______.

A

0

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

An AVL imbalance that occurs when inserting into the right subtree of the left child is called the ______ case.

A

RL (Right-Left case)

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

In the First-Child / Next-Sibling representation, each node has two pointers: ______ and ______.

A

firstChild and nextSibling

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

A BST search stops when a null child is reached, meaning the element is ______.

A

null

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

Heap sort using a max-heap produces the final array in ______ order.

A

ascending

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

A forest is defined as:
A. A tree with no root
B. A tree with many roots
C. A collection of disjoint trees
D. A tree with cycles

A

C. A collection of disjoint trees

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

The depth of a node is the length of the path from the ______.
A. Node to any leaf
B. Node to its parent
C. Root to the node
D. Node to its sibling

A

C. Root to the node

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

Which representation requires k pointers per node?
A. First-child / next-sibling
B. k-ary tree representation
C. Parent-pointer only
D. Array representation

A

B. k-ary tree representation

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

In an almost complete binary tree, missing nodes appear only on the ______.
A. Left side
B. Right side
C. Root
D. Middle

A

B. Right side

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Which traversal is naturally implemented with a queue? A. Preorder B. Inorder C. Postorder D. Breadth-first
D. Breadth-first
22
Which of the following is true for binary search trees? A. Left subtree keys > root B. Right subtree keys < root C. Left subtree keys < root D. No ordering rules
C. Left subtree keys < root
23
Deleting a BST node with one child requires: A. Removing node and connecting child to the parent B. Replacing it with the in-order successor C. Replacing it with the root D. Swapping with a leaf then deleting
A. Removing node and connecting child to the parent
24
A rotation in AVL trees is used to: A. Maintain height balance B. Sort the keys C. Remove duplicates D. Build a heap
A. Maintain height balance
25
Which rotation fixes a Right-Right (RR) imbalance? A. Right rotation B. Right-Left rotation C. Left-Right rotation D. Left rotation
D. Left rotation
26
A heap must always be structured as: A. A complete or almost complete binary tree B. A BST C. A full binary tree D. A balanced multi-way tree
A. A complete or almost complete binary tree
27
In a max-heap, the highest priority element is always located at: A. The last index B. Any leaf C. The root D. The leftmost child
C. The root
28
Which set operation returns elements that are in A but not in B? A. Intersection B. Difference C. Complement D. Union
B. Difference
29
A node with no children is called a ______.
Leaf/Terminal Vertex
30
The children of a node are considered ______ of that node.
descendants
31
A complete binary tree of height h has at most ______ nodes.
2^(h+1)-1
32
In an array-based heap, the left child of index i is at index ______.
2i
33
A BST search that tries to go past a leaf ends at a ______ pointer.
null
34
The balance factor of an AVL node is: height(left subtree) − height(______) subtree.
right
35
Heapify-down is used after ______ the root of a max-heap.
deleting
36
A set can be represented by a string of bits called a ______ vector.
bit-string
37
Which of the following is NOT a property of trees? A. Connected B. Acyclic C. Exactly one simple path between any two nodes D. Has at least one cycle
D. Has at least one cycle
38
The height of a node is defined as the length of the longest path from the root to a ______. A. Parent B. Child C. Leaf D. Sibling
C. Leaf
39
In first-child/next-sibling representation, the children of a node form a ______. A. Circular list B. Linked list C. Binary tree D. Heap
B. Linked list
40
Which binary tree type guarantees all leaves at the same level? A. Perfect B. Complete C. Full D. Almost complete
A. Perfect
41
Which traversal is Visit → Left → Right? A. Preorder B. Inorder C. Postorder D. Level order
A. Preorder
42
Which statement about BSTs is FALSE? A. Searching is O(log n) in balanced cases B. Searching is O(n) in worst cases C. Insertion always takes O(1) D. Deletion may require replacing a node
C. Insertion always takes O(1)
43
Which of the following is the in-order successor of a node with two children? A. Rightmost node in left subtree B. Leftmost node in right subtree C. Root node D. Any leaf
B. Leftmost node in right subtree
44
Which imbalance in AVL trees requires a Right-Left (RL) rotation? A. Inserted into left subtree of left child B. Inserted into right subtree of left child C. Inserted into left subtree of right child D. Inserted into right subtree of right child
C. Inserted into left subtree of right child
45
Which data structure always satisfies the heap-order property? A. BST B. Hash table C. Heap D. AVL tree
C. Heap
46
In a max-heap, which operation moves a node downward to restore the heap? A. heapifyUp B. rotateLeft C. heapifyDown D. siftLeft
C. heapifyDown
47
The array index of the right child of node i in a binary heap is: A. i – 1 B. 2i C. 2i + 1 D. 3i – 1
C. 2i + 1
48
Which set operation selects elements that are in BOTH A and B? A. Union B. Intersection C. Complement D. Symmetric difference
B. Intersection
49
A tree with no children at the root and no other nodes is called a ______ node.
leaf
50
The degree of a vertex refers to the number of its ______.
children
51
A full binary tree with I internal nodes has exactly ______ leaves.
I + 1
52
In an almost complete binary tree, nodes are filled from left to right, but holes may exist only at the ______ end.
last
53
In preorder traversal, the first node visited is always the ______.
root
54
A BST stores elements so that every key in the right subtree is ______ than the root.
less
55
An AVL tree requires a rotation whenever the balance factor becomes less than −1 or greater than ______.
1
56
In heap sort, after extracting the maximum element and swapping, we perform ______ to restore the heap.
heapifyDown
DSA
flashcards
Decks in class (22)
# Cards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2026 Bold Learning Solutions. Terms and Conditions