Font size
WorksheetsBinary Tree Quiz
Total questions: 144
Worksheet time: 1hrs 15mins
What is the maximum number of children that a binary tree node can have?
0
1
2
3
The following tree is an example of?
Binary tree
Binary search tree
Fibonacci tree
None
How many common operations are performed in a binary tree?
1
2
3
4
What is the traversal strategy used in a binary tree?
depth-first traversal
breadth-first traversal
random traversal
priority traversal
How many types of insertions are performed in a binary tree?
1
2
3
4
What operation does the following diagram depict?
Inserting a leaf node
Inserting an internal node
Deleting a node with 0 or 1 child
None
How many bits would a succinct binary tree occupy?
n + O(n)
2n + O(n)
n / 2
n
The average depth of a binary tree is given as?
O(N)
O(√N)
O(N2)
O(log N)
How many orders of traversal are applicable to a binary tree (in general)?
1
4
2
3
If binary trees are represented in arrays, what formula can be used to locate a left child if the node has an index i?
2i+1
2i+2
2i
4i
Using what formula can a parent node be located in an array?
(i+1)/2
(i-1)/2
i/2
2i/2
Which of the following properties are obeyed by all three tree traversals?
Left subtrees are visited before right subtrees
Right subtrees are visited before left subtrees
Root node is visited before left subtree
Root node is visited before right subtree
For the tree below, write the pre-order traversal.
2, 7, 2, 6, 5, 11, 5, 9, 4
2, 7, 5, 2, 6, 9, 5, 11, 4
2, 5, 11, 6, 7, 4, 9, 5, 2
none
For the tree below, write the post-order traversal.
2, 7, 2, 6, 5, 11, 5, 9, 4
2, 7, 5, 2, 6, 9, 5, 11, 4
2, 5, 11, 6, 7, 4, 9, 5, 2
none
What is the time complexity of pre-order traversal in the iterative fashion?
O(1)
O(n)
O(log n)
O(n log n)
What is the space complexity of post-order traversal in a recursive fashion? (d is the tree depth and n is the number of nodes)
O(1)
O(nlogd)
O(logd)
O(d)
To obtain a prefix expression, which tree traversal is used?
Level-order traversal
Pre-order traversal
Post-order traversal
In-order traversal
Consider the following data. The pre-order traversal of a binary tree is A, B, E, C, D. The in-order traversal of the same binary tree is B, E, A, D, C. The level order sequence for the binary tree is
A, C, D, B, E
A, B, C, D, E
A, B, C, E, D
D, B, E, A, C
What is the possible number of binary trees that can be created with 3 nodes, giving the sequence N, M, L when traversed in post-order?
15
3
5
8
The post-order traversal of a binary tree is O P Q R S T. Then the possible pre-order traversal will be
T Q R S O P
T O Q R P S
T Q O P S R
T Q O S P R
A binary search tree contains the values 7, 8, 13, 26, 35, 40, 70, and 75. Which one of the following is a valid post-order sequence of the tree, given the pre-order sequence as 35, 13, 7, 8, 26, 70, 40, and 75?
7, 8, 26, 13, 75, 40, 70, 35
26, 13, 7, 8, 70, 75, 40, 35
7, 8, 13, 26, 35, 40, 70, 75
8, 7, 26, 13, 40, 75, 70, 35
Which of the following pairs' traversals on a binary tree can build the tree uniquely?
post-order and pre-order
post-order and in-order
post-order and level order
level order and pre-order
A full binary tree can be generated using
post-order and pre-order traversal
pre-order traversal
post-order traversal
in-order traversal
The maximum number of nodes in a tree for which post-order and pre-order traversals may be equal is
3
1
2
any number
The pre-order and in-order traversals of a binary tree are T M L N P O Q and L M N T O P Q. Which of the following is the post-order traversal of the tree?
L N M O Q P T
N M O P O L T
L M N O P Q T
O P L M N Q T
Find the postorder traversal of the binary tree shown below.
P Q R S T U V W X
W R S Q P V T U X
S W T Q X U V R P
None
For the tree below, write the in-order traversal.
6, 2, 5, 7, 11, 2, 5, 9, 4
6, 5, 2, 11, 7, 4, 9, 5, 2
2, 7, 2, 6, 5, 11, 5, 9, 4
none
For the tree below, write the level-order traversal.
2, 7, 2, 6, 5, 11, 5, 9, 4
2, 7, 5, 2, 11, 9, 6, 5, 4
2, 5, 11, 6, 7, 4, 9, 5, 2
none
What is the space complexity of the in-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes)
O(1)
O(n log d)
O(log d)
O(d)
What is the time complexity of level order traversal?
O(1)
O(n)
O(log n)
O(n log n)
Which of the following graph traversals closely imitates the level order traversal of a binary tree?
Depth First Search
Breadth First Search
Depth & Breadth First Search
Binary Search
In a binary search tree, which of the following traversals would print the numbers in ascending order?
Level-order traversal
Pre-order traversal
Post-order traversal
In-order traversal
The number of edges from the root to the node is called the depth of the tree.
Height
Depth
Length
Width
The number of edges from the node to the deepest leaf is called the height of the tree.
Height
Depth
Length
Width
What is a full binary tree?
Each node has exactly zero or two children
Each node has exactly two children
All the leaves are at the same level
Each node has exactly one or two children
What is a complete binary tree?
Each node has exactly zero or two children
A binary tree that is completely filled, with the possible exception of the bottom level, which is filled from right to left
A binary tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right
A tree in which all nodes have degree 2
What is the average case time complexity for finding the height of a binary tree?
h = O(loglogn)
h = O(nlogn)
h = O(n)
h = O(log n)
Which of the following is not an advantage of trees?
Hierarchical structure
Faster search
Router algorithms
Undo/Redo operations in a notepad
In a full binary tree, if the number of internal nodes is I, then the number of leaves L is?
L = 2*I
L = I + 1
L = I - 1
L = 2*I - 1
In a full binary tree, if the number of internal nodes is I, then the number of nodes N is?
N = 2*I
N = I + 1
N = I - 1
N = 2*I + 1
In a full binary tree, if there are L leaves, then the total number of nodes N is?
N = 2*L
N = L + 1
N = L - 1
N
In a full binary tree, if there are L leaves, then the total number of nodes N is?
N = 2*L
N = L + 1
N = L - 1
N = 2*L - 1
Which of the following is incorrect with respect to binary trees?
Let T be a binary tree. For every k ≥ 0, there are no more than 2k nodes in level k
Let T be a binary tree with λ levels. Then T has no more than 2λ - 1 nodes
Let T be a binary tree with N nodes. Then the number of levels is at least ceil(log (N + 1))
Let T be a binary tree with N nodes. Then the number of levels is at least floor(log (N + 1))
Which of the following is false about a binary search tree?
The left child is always less than its parent
The right child is always greater than its parent
The left and right subtrees should also be binary search trees
In-order traversal gives decreasing order of elements
What is the specialty of the inorder traversal of a binary search tree?
It traverses in a non-increasing order
It traverses in an increasing order
It traverses in a random fashion
It traverses based on the priority of the node
What are the worst-case and average-case complexities of a binary search tree?
O(n), O(n)
O(logn), O(logn)
O(logn), O(n)
O(n), O(logn)
What are the conditions for an optimal binary search tree and what is its advantage?
The tree should not be modified, and you should know how often the keys are accessed; it improves the lookup cost.
You should know the frequency of access of the keys; it improves the lookup time.
The tree can be modified, and you should know the number of elements in the tree beforehand; it improves the deletion time.
The tree should just be modified and improves the lookup time.
Which of the following is not a self-balancing binary search tree?
AVL Tree
2-3-4 Tree
Red-Black Tree
Splay Tree
The binary tree sort implemented using a self-balancing binary search tree takes time in the worst case.
O(n log n)
O(n)
O(n2)
O(log n)
An AVL tree is a self-balancing binary search tree, in which the heights of the two child subtrees of any node differ by
At least one
At most one
Two
At most two
Associative arrays can be implemented using
B-tree
A doubly linked list
A single linked list
A self balancing binary search tree
Which of the following is a self - balancing binary search tree?
2-3 tree
Threaded binary tree
AA tree
Treap
A self - balancing binary search tree can be used to implement
Priority queue
Hash table
Heap sort
Priority queue and Heap sort
In which of the following self - balancing binary search tree the recently accessed element can be accessed quickly?
AVL tree
AA tree
Splay tree
Red - Black tree
The minimum height of self balancing binary search tree with n nodes is
log2(n)
n
2n + 1
2n - 1
What is an AVL tree?
a tree which is balanced and is a height balanced tree
a tree which is unbalanced and is a height balanced tree
a tree with three children
a tree with atmost 3 children
Why we need to a binary tree which is height balanced?
to avoid formation of skew trees
to save memory
to attain faster memory access
to simplify storing
What is the maximum height of an AVL tree with p nodes?
p
log(p)
log(p)/2
P⁄2
Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations?
just build the tree with the given input
find the median of the set of elements given, make it as root and construct the tree
use trial and error
use dynamic programming to build the tree
What maximum difference in heights between the leafs of a AVL tree is possible?
log(n) where n is the number of nodes
n where n is the number of nodes
0 or 1
atmost 1
What is missing?
Height(w-left), x-height
Height(w-right), x-height
Height(w-left), x
Height(w-left)
Why to prefer red-black trees over AVL trees?
Because red-black is more rigidly balanced
AVL tree store balance factor in every node which costs space
AVL tree fails at scale
Red black is more efficient
Which of the following is the most widely used external memory data structure?
AVL tree
B-tree
Red-black tree
Both AVL tree and Red-black tree
B-tree of order n is a order-n multiway tree in which each non-root node contains
at most (n - 1)/2 keys
exact (n - 1)/2 keys
at least 2n keys
at least (n - 1)/2 keys
A B-tree of order 4 and of height 3 will have a maximum of keys.
255
63
127
188
Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written?
14
7
11
5
trees are B-trees of order 4. They are an isometric of trees.
AVL
AA
2-3
Red-Black
What is the best case height of a B-tree of order n and which has k keys?
logn (k+1) - 1
nk
logk (n+1) - 1
klogn
Which of the following is true?
larger the order of B-tree, less frequently the split occurs
larger the order of B-tree, more frequently the split occurs
smaller the order of B-tree, more frequently the split occurs
smaller the order of B-tree, less frequently the split occurs
What is the best case for linear search?
What is the best case for linear search?
O(nlogn)
O(logn)
O(n)
O(1)
What is the worst case for linear search?
O(nlogn)
O(logn)
O(n)
O(1)
What is the best case and worst case complexity of ordered linear search?
O(nlogn), O(logn)
O(logn), O(nlogn)
O(n), O(1)
O(1), O(n)
Which of the following is a disadvantage of linear search?
Requires more space
Greater time complexities compared to other searching algorithms
Not easy to understand
Not easy to implement
Which of the following statements for a simple graph is correct?
Every path is a trail
Every trail is a path
Every trail is a path as well as every path is a trail
Path and trail have no relation
For the given graph(G), which of the following statements is true?
G is a complete graph
G is not a connected graph
The vertex connectivity of the graph is 2
none
What is the number of edges present in a complete graph having n vertices?
(n*(n+1))/2
(n*(n-1))/2
n
Information given is insufficient
The given Graph is regular.
True
False
none
none
A connected planar graph having 6 vertices, 7 edges contains regions.
15
3
1
11
If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is
(n*n-n-2*m)/2
(n*n+n+2*m)/2
(n*n-n-2*m)/2
(n*n-n+2*m)/2
Which of the following properties does a simple graph not hold?
Must be connected
Must be unweighted
Must have no loops or multiple edges
Must have no multiple edges
What is the maximum number of edges in a bipartite graph having 10 vertices?
24
21
25
16
Which of the following is true?
A graph may contain no edges and many vertices
A graph may contain many edges and no vertices
A graph may contain no edges and no vertices
A graph may contain no vertices and many edges
For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true?
v=e
v = e+1
v + 1 = e
v = e-1
For which of the following combinations of the degrees of vertices would the connected graph be eulerian?
1,2,3
2,3,4
2,4,5
1,3,5
A graph with all vertices having equal degree is known as a
Multi Graph
Regular Graph
Simple Graph
Complete Graph
Which of the following ways can be used to represent a graph?
Adjacency List and Adjacency Matrix
Incidence Matrix
Adjacency List, Adjacency Matrix as well as Incidence Matrix
No way to represent
The number of possible undirected graphs which may have self loops but no multiple edges and have n vertices is
2((n*(n-1))/2)
2((n*(n+1))/2)
2((n-1)*(n-1))/2)
2((n*n)/2)
Given a plane graph, G having 2 connected component, having 6 vertices, 7 edges and 4 regions. What will be the number of connected components?
1
2
3
4
Number of vertices with odd degrees in a graph having a eulerian walk is
0
Can't be predicted
2
either 0 or 2
How many of the following statements are correct?
All cyclic graphs are complete graphs.
All complete graphs are cyclic graphs.
All paths are bipartite.
All cyclic graphs are bipartite.
What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.
n-2
n
2
0
What would the time complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix?
O(E*E)
O(V*V)
O(E)
O(V)
With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?
(V*(V-1))/2
(V*(V+1))/2
(V+1)C2
(V-1)C2
The topological sorting of any DAG can be done in time.
cubic
quadratic
linear
logarithmic
If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
Many Hamiltonian paths are possible
No Hamiltonian path is possible
Exactly 1 Hamiltonian path is possible
Given information is insufficient to comment anything
Which of the given statement is true?
All the Cyclic Directed Graphs have topological sortings
All the Acyclic Directed Graphs have topological sortings
All Directed Graphs have topological sortings
All the cyclic directed graphs have non topological sortings
What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?
Depends on a Graph
Will always be zero
Will always be greater than zero
May be zero or greater than zero
Which data structure is typically used to implement breadth-first search (BFS) in a graph?
Array
Stack
Queue
Linked List
Which of the following is a characteristic of a binary search tree (BST)?
Nodes have at most two children
Each node stores multiple values
Unordered structure
Allows cycles
Which tree type maintains a balance by enforcing constraints on its nodes?
B-Tree
AVL Tree
Red-Black Tree
Binary Tree
What is the primary purpose of a hash table in computer science?
To represent hierarchical relationships
To store data dynamically
To store data in an unordered manner for fast access
To store elements in order
Which of these is not an example of a balanced binary search tree?
Binary Tree
AVL Tree
Red-Black Tree
B-Tree
In which of the following scenarios would a priority queue be useful?
Sorting a list of items
Handling elements based on priority
Managing function calls in recursion
Storing large datasets
What is the worst-case time complexity of quicksort?
O(n)
O(n log n)
O(log n)
O(n²)
What does a min-heap property ensure?
The root contains the minimum element
Each node is larger than its children
The tree is perfectly balanced
The root contains the maximum element
What is the main feature of a circular linked list?
Elements are sorted
Last node points to the first node
Nodes have two pointers
List has a fixed size
What is the purpose of the depth-first search (DFS) algorithm in graph theory?
To find the shortest path
To check for cycles
To visit all nodes by exploring as deep as possible
To find the maximum node value
Which data structure is used for efficient dynamic memory allocation?
Linked List
Hash Table
Queue
Stack
Which of the following sorting algorithms is in-place?
Bubble Sort
Quick Sort
Merge Sort
none
Which type of data structure is used to implement recursion?
Array
Tree
Stack
Linked List
Which of the following trees allows for efficient insertion, deletion, and search operations with a logarithmic time complexity?
AVL Tree
Red-Black Tree
B-Tree
All of the above
What is a tree in data structures?
A linear data structure
A non-linear data structure
A type of array
A fixed-size data structure
What is the maximum number of children a binary tree node can have?
One
Two
Three
Unlimited
What is the height of a tree?
The number of nodes
The number of edges from the root to the farthest leaf
The total number of levels
The number of leaf nodes
In a binary tree, what is the maximum number of nodes at level n?
n
2^n
2^(n-1)
n^2
What is a full binary tree?
A tree with all levels fully filled
A tree where every node has either 0 or 2 children
A tree with a single path from root to leaf
A tree with at least one leaf node
What is a complete binary tree?
A tree where all nodes have two children
A tree where all levels are fully filled except possibly the last
A tree with no leaf nodes
A binary tree with only one path
What is the purpose of a binary search tree (BST)?
To store data in a non-linear format
To allow efficient searching, insertion, and deletion
To keep elements sorted
All of the above
What is the in-order traversal of a binary tree?
Visit the root, then left subtree, then right subtree
Visit the left subtree, then root, then right subtree
Visit the right subtree, then root, then left subtree
Visit nodes in level order
What is the pre-order traversal of a binary tree?
Visit the left subtree, then root, then right subtree
Visit the root, then left subtree, then right subtree
Visit the right subtree, then root, then left subtree
Visit nodes in level order
What is the post-order traversal of a binary tree?
Visit the left subtree, then root, then right subtree
Visit the root, then left subtree, then right subtree
Visit the left subtree, then right subtree, then root
Visit nodes in level order
What is the worst-case time complexity for searching in a binary search tree?
O(1)
O(log n)
O(n)
O(n log n)
Which of the following is NOT a property of a binary search tree?
Left subtree nodes are less than the root
Right subtree nodes are greater than the root
All nodes must have two children
Each subtree must also be a binary search tree
What is the minimum height of a binary tree with n nodes?
log(n)
n
log(n + 1)
n - 1
What is a balanced binary tree?
A tree where all leaf nodes are at the same level
A tree where the height difference between left and right subtrees is no more than one
A tree that is complete
A tree where every node has two children
What is a binary heap?
A complete binary tree that satisfies the heap property
A type of binary search tree
A linear data structure
A tree with random node arrangement
What is the space complexity for storing a binary tree?
O(n)
O(log n)
O(1)
O(n log n)
Which traversal method is used to sort a binary search tree?
In-order traversal
Pre-order traversal
Post-order traversal
Level-order traversal
What is the level of a node in a tree?
The number of edges from the root to the node
The height of the node
The total number of nodes
The depth of the node
What is a leaf node in a tree?
A node with no children
A node with one child
A node with two children
A node that is the root
Which data structure can be used to implement a tree?
Array
Linked list
Both A and B
None of the above
What is the breadth-first search (BFS) traversal of a tree?
Level-order traversal
Pre-order traversal
In-order traversal
Post-order traversal
What is a binary tree with all nodes having 0 or 1 child called?
Complete binary tree
Full binary tree
Degenerate tree
Balanced binary tree
What is the depth of a node in a tree?
The number of nodes from the root to the node
The number of edges from the root to the node
The height of the tree
The level of the tree
What is a B-tree?
A binary search tree
A self-balancing tree that maintains sorted data
A complete binary tree
A type of heap
What is the height of a balanced binary tree with n nodes?
log(n)
n
n/2
log(n + 1)
What is a Red-Black tree?
A type of binary search tree
A self-balancing binary search tree
A binary heap
A complete binary tree
What is the main advantage of using a self-balancing tree?
It requires less memory
It maintains a balanced structure for efficient operations
It is easier to implement
It allows for random access
What is a thread in a threaded binary tree?
A pointer to the next node in in-order traversal
A pointer to the parent node
A pointer to a child node
A pointer to the root node
What type of tree is used to implement a priority queue?
Binary search tree
AVL tree
Binary heap
Red-Black tree
What is the main characteristic of a ternary tree?
Each node has up to three children
Each node has up to two children
It is a complete binary tree
It is a degenerate tree
What type of traversal uses a stack?
Breadth-first search
Depth-first search
In-order traversal
Both B and C
What is the primary characteristic of a Splay tree?
It is self-balancing
It uses rotation to move frequently accessed nodes closer to the root
