New 80 Tree Interview Questions
Introduction
Tree interview questions are commonly asked in programming and technical interviews. Trees are a fundamental data structure used to organize and store data in a hierarchical manner. In these interviews, you may be asked to solve problems related to tree traversal, searching, insertion, deletion, or other tree operations. It’s important to understand the concepts of nodes, parents, children, and leaves in a tree, as well as different types of trees like binary trees and binary search trees. These questions test your problem-solving skills, data structure knowledge, and ability to manipulate tree structures efficiently. With practice and understanding, you can excel in tree interview questions and demonstrate your expertise in handling complex data structures.
Theory Questions
1. What is a tree data structure?
A tree is a hierarchical data structure that consists of nodes connected by edges. It starts with a root node and each node can have zero or more child nodes. The nodes in a tree are organized in a parent-child relationship, where each node (except the root) has exactly one parent node, and each node can have multiple child nodes.
2. What is a binary tree?
A binary tree is a special type of tree in which each node has at most two children: a left child and a right child. The binary tree is one of the most commonly used data structures due to its simplicity and efficient searching, insertion, and deletion operations.
3. What are the different types of binary trees?
There are several different types of binary trees, some of the common ones include:
- Full binary tree: A binary tree in which every node has either 0 or 2 children, and all leaf nodes are at the same level.
- Complete binary tree: A binary tree where all levels are completely filled, except possibly the last level, which is filled from left to right.
- Perfect binary tree: A binary tree in which all internal nodes have two children, and all leaf nodes are at the same level.
- Balanced binary tree: A binary tree where the difference in height between the left and right subtrees of any node is not greater than one.
4. What is the difference between a binary tree and a binary search tree?
The main difference between a binary tree and a binary search tree (BST) lies in their structural property and the ordering of nodes:
- Binary Tree: A binary tree is a hierarchical data structure with at most two children per node. There are no specific ordering rules for the nodes.
- Binary Search Tree (BST): A BST is a binary tree with the added property that for every node, all nodes in its left subtree have values less than the node’s value, and all nodes in its right subtree have values greater than the node’s value. This ordering makes searching, insertion, and deletion operations efficient.
5. What is the maximum number of nodes in a binary tree of height ‘h’?
The maximum number of nodes in a binary tree of height ‘h’ can be calculated using the formula: 2^(h+1) – 1.
// Calculate the maximum number of nodes in a binary tree of height 'h'
int maxNodesInBinaryTree(int height) {
return (1 << (height + 1)) - 1;
}6. What is a balanced binary tree?
A balanced binary tree is a binary tree in which the difference in height between the left and right subtrees of any node is not greater than one. In other words, the height difference between the left and right subtrees is limited, which helps to ensure efficient operations on the tree, such as searching, insertion, and deletion.
7. Explain the concept of tree traversal. What are the different types of tree traversal?
Tree traversal refers to the process of visiting all the nodes in a tree data structure in a specific order. There are two main types of tree traversal:
- Depth-First Traversal: In this traversal, we explore as far as possible along each branch before backtracking. There are three common approaches:
- In-order traversal: Visit the left subtree, then the root node, and finally the right subtree.
- Pre-order traversal: Visit the root node, then the left subtree, and finally the right subtree.
- Post-order traversal: Visit the left subtree, then the right subtree, and finally the root node.
- Breadth-First Traversal: In this traversal, we visit all the nodes at the current level before moving on to the next level. It uses a queue data structure to keep track of the nodes to be visited.
// Node structure for a binary tree
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
// In-order traversal (recursive)
void inOrderTraversal(Node* root) {
if (root) {
inOrderTraversal(root->left);
cout << root->data << " ";
inOrderTraversal(root->right);
}
}
// Pre-order traversal (recursive)
void preOrderTraversal(Node* root) {
if (root) {
cout << root->data << " ";
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
// Post-order traversal (recursive)
void postOrderTraversal(Node* root) {
if (root) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
cout << root->data << " ";
}
}
// Breadth-First Traversal (using a queue)
void breadthFirstTraversal(Node* root) {
if (!root)
return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
cout << current->data << " ";
if (current->left)
q.push(current->left);
if (current->right)
q.push(current->right);
}
}8. What is a depth-first search (DFS) in the context of trees?
Depth-First Search (DFS) is a technique used for traversing or searching tree data structures. It starts from the root node and explores as far as possible along each branch before backtracking. There are three common DFS strategies for binary trees: in-order, pre-order, and post-order traversals, which were explained in question 7.
9. What is a breadth-first search (BFS) in the context of trees?
Breadth-First Search (BFS) is another technique used for traversing tree data structures. It starts from the root node and visits all the nodes at the current level before moving on to the next level. BFS uses a queue data structure to keep track of the nodes to be visited, ensuring that nodes at higher levels are visited before those at lower levels.
10. What are the applications of trees in computer science?
Trees have various applications in computer science due to their hierarchical and organized structure. Some common applications include:
- Storing hierarchical data: File systems, XML representation, organization charts.
- Searching and sorting: Binary search trees, AVL trees, and red-black trees for efficient searching and sorting operations.
- Compiler construction: Expression trees for evaluating expressions and syntax trees for parsing and compilation.
- Network routing algorithms: Hierarchical routing in computer networks.
- Data compression: Huffman coding based on Huffman trees.
- Decision-making algorithms: Decision trees in machine learning for classification and regression tasks.
11. What is a self-balancing binary search tree?
A self-balancing binary search tree is a type of binary search tree that automatically maintains its balance during insertions and deletions to ensure that the tree remains relatively balanced. This balance is crucial to maintain efficient search, insertion, and deletion operations. Common examples of self-balancing binary search trees include AVL trees, red-black trees, and splay trees.
12. What is an AVL tree?
An AVL tree is a self-balancing binary search tree. It ensures that the height difference between the left and right subtrees of every node (known as the balance factor) is not greater than one. Whenever an insertion or deletion causes an imbalance, AVL trees perform rotations to restore the balance. This ensures that the tree height remains logarithmic, making search, insert, and delete operations efficient.
13. What is a red-black tree?
A red-black tree is another type of self-balancing binary search tree. It ensures that the tree is approximately balanced by enforcing five properties:
- Every node is either red or black.
- The root and leaves (null nodes) are black.
- Red nodes have black children.
- All paths from a node to its descendant leaves contain the same number of black nodes.
- A new node inserted is always red.
14. What is a B-tree?
A B-tree is a balanced tree data structure designed to maintain large and sorted datasets efficiently. It is commonly used in databases and file systems, where it can handle large amounts of data and allow for efficient search, insertion, and deletion operations. B-trees have a variable number of child nodes per internal node, and they maintain certain properties to ensure balance and efficiency.
15. What is a trie (prefix tree) and what is it used for?
A trie, also known as a prefix tree, is a specialized tree data structure used for efficient storage and retrieval of strings and dynamic sets. It is particularly useful for tasks involving string matching, prefix searching, and autocomplete suggestions. In a trie, each node represents a single character, and the path from the root to a node represents a string. Tries optimize memory usage by sharing common prefixes among multiple strings.
16. What is a heap and what is a binary heap?
A heap is a specialized binary tree-based data structure that satisfies the heap property. The heap property ensures that for every node in the heap, the value of the node is either greater than or equal to (max heap) or less than or equal to (min heap) the values of its children.
A binary heap is a specific type of heap implemented as a binary tree. It can be either a max heap or a min heap. In a max heap, the value of each node is greater than or equal to the values of its children, and the maximum value is stored at the root node. In a min heap, the value of each node is less than or equal to the values of its children, and the minimum value is stored at the root node.
17. Explain the Heap property in the context of binary heaps.
The heap property in the context of binary heaps ensures that the relationship between parent and child nodes is maintained. In a max heap, for every node ‘A’, the value of ‘A’ is greater than or equal to the values of its left and right children. In other words, the maximum value is stored at the root, and the values decrease as we move down the heap.
In a min heap, for every node ‘A’, the value of ‘A’ is less than or equal to the values of its left and right children. Hence, the minimum value is stored at the root, and the values increase as we move down the heap.
18. What is a Cartesian tree?
A Cartesian tree, also known as a Cartesian binary tree, is a special type of binary tree that can be constructed from an array of values. It is built based on the Cartesian coordinates of the points in a two-dimensional plane. In this tree, each node represents an element from the array, and the tree has the following properties:
- The value of the node is equal to the array element it represents.
- The Cartesian tree satisfies the heap property, making it a binary heap.
19. What are splay trees and what are their applications?
Splay trees are a type of self-adjusting binary search tree in which recently accessed nodes are moved closer to the root, making them easier to access again in the future. The splay operation, which is applied after each access, reorganizes the tree by performing rotations to bring the accessed node to the root position. This operation helps improve the overall performance of frequently accessed nodes.
Splay trees find applications in caching, memory management, and various other scenarios where frequently accessed items need to be accessed faster.
20. What are segment trees and what are their applications?
A segment tree is a tree data structure used for efficiently handling range queries and updates on an array or list. It is particularly useful for problems involving finding the sum, minimum, maximum, or other aggregate functions over a range of elements in an array.
Segment trees find applications in problems like range sum queries, range minimum queries, and range maximum queries in competitive programming and other areas where efficient range queries are required.
21. What is the difference between a binary tree and a k-ary tree?
A binary tree is a special case of a k-ary tree where each node can have at most two children: a left child and a right child. In contrast, a k-ary tree is a tree in which each node can have up to ‘k’ children.
For example, in a binary tree, ‘k’ is 2, meaning each node can have at most 2 children. In a ternary tree (3-ary tree), each node can have up to 3 children, and so on.
22. What are Fenwick trees (Binary Indexed Trees) and what are their applications?
Fenwick trees, or Binary Indexed Trees (BIT), are data structures designed to perform cumulative frequency queries and updates on an array efficiently. They are instrumental when dealing with prefix sums and range updates in arrays.
Fenwick trees are widely used in problems involving frequent updates and queries on cumulative frequencies, such as finding the sum of elements in a prefix of an array or updating individual elements in the array efficiently.
23. How is the concept of a tree used in networking (e.g., routing algorithms, multicast)?
In networking, the concept of a tree is used in various ways, particularly in routing algorithms and multicast communication.
- Routing Algorithms: In computer networks, routing algorithms use tree-based data structures to determine the most efficient path for data packets to travel from the source to the destination. One such example is the Spanning Tree Protocol (STP), used to prevent loops in Ethernet networks.
- Multicast: Multicast communication involves sending data to multiple recipients simultaneously. A multicast tree is often used to efficiently deliver data to all members of a multicast group. The tree is constructed such that data is forwarded only to the necessary branches to reach all recipients.
24. What are expression trees and how are they used in compilers?
Expression trees are binary trees used to represent mathematical expressions or arithmetic expressions. Each node in the tree represents an operator or an operand, and the tree’s structure mirrors the hierarchical arrangement of the expression.
In compilers, expression trees are utilized during the process of parsing and evaluating expressions. Once the source code is parsed and converted into an expression tree, the compiler can efficiently evaluate the expression, perform optimizations, and generate machine code accordingly.
25. What is Huffman coding and how does it relate to trees?
Huffman coding is a data compression technique that uses variable-length encoding for different characters in a given input. It aims to reduce the overall number of bits required to represent the input data efficiently.
Huffman coding relies on the concept of Huffman trees, which are specific binary trees used to generate optimal prefix codes for characters based on their frequencies in the input data. Characters with higher frequencies are assigned shorter codes, while characters with lower frequencies are assigned longer codes. This way, frequent characters use fewer bits, leading to compression.
26. What is the concept of tree rotation?
Tree rotation is an operation performed on certain types of binary trees to maintain or restore their balance after insertions or deletions. The two most common types of rotations are left rotation and right rotation.
- Left Rotation: It involves rotating a binary tree to the left around a specific node. This operation is used to restore the balance of a binary search tree when the right subtree becomes taller than the left subtree.
- Right Rotation: It involves rotating a binary tree to the right around a specific node. This operation is used to restore the balance of a binary search tree when the left subtree becomes taller than the right subtree.
27. What is a suffix tree and what is it used for?
A suffix tree is a tree-based data structure used to efficiently store all the suffixes of a given string. It is mainly used in string processing and pattern matching algorithms, such as finding repeated substrings, pattern searching, and substring matching.
Suffix trees have applications in areas like bioinformatics, text indexing, and data compression. They allow for quick searches for patterns and substrings in large texts, making them valuable tools in various computational tasks.
28. What are decision trees in the context of machine learning?
Decision trees are a popular machine learning algorithm used for both classification and regression tasks. They are tree-like structures where each internal node represents a decision based on a feature, each branch represents the outcome of the decision, and each leaf node represents the predicted class or value.
Decision trees work by recursively splitting the data into subsets based on the input features, aiming to maximize the information gain or minimize impurity at each split. The resulting tree can be used to make predictions on new data by following the path from the root to a leaf node based on the feature values of the data.
29. What is tree pruning in decision tree algorithms?
Tree pruning is a technique used in decision tree algorithms to prevent overfitting and improve the model’s generalization capability. Overfitting occurs when a decision tree is too complex and captures noise or outliers in the training data, leading to poor performance on unseen data.
Pruning involves removing certain branches or subtrees from the decision tree that do not contribute significantly to improving its performance on the validation data. This simplifies the tree and helps in avoiding overfitting, resulting in a more generalized and accurate model.
30. What is the concept of recursion and how is it applied in tree operations?
Recursion is a programming technique where a function calls itself to solve smaller instances of a problem. In the context of tree operations, recursion is widely used for tree traversals, searching, and other recursive algorithms.
For example, in binary tree traversals like in-order, pre-order, and post-order, the traversal can be performed recursively by visiting the left subtree, then the root, and finally the right subtree (or vice versa). The recursion continues until the base case is reached, which is usually when the current node is null.
Coding Questions
1. Calculate the height of a binary tree.
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};
int heightOfBinaryTree(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftHeight = heightOfBinaryTree(root->left);
int rightHeight = heightOfBinaryTree(root->right);
return 1 + max(leftHeight, rightHeight);
}2. Check if a binary tree is balanced.
bool isBalanced(TreeNode* root) {
if (root == nullptr) {
return true;
}
int leftHeight = heightOfBinaryTree(root->left);
int rightHeight = heightOfBinaryTree(root->right);
if (abs(leftHeight - rightHeight) <= 1 && isBalanced(root->left) && isBalanced(root->right)) {
return true;
}
return false;
}3. Determine if a tree is a binary search tree.
bool isBSTHelper(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
if (root == nullptr) {
return true;
}
if ((minNode && root->val <= minNode->val) || (maxNode && root->val >= maxNode->val)) {
return false;
}
return isBSTHelper(root->left, minNode, root) && isBSTHelper(root->right, root, maxNode);
}
bool isBinarySearchTree(TreeNode* root) {
return isBSTHelper(root, nullptr, nullptr);
}4. Find the least common ancestor of two nodes in a binary tree.
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) {
return root;
}
TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);
TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);
if (leftLCA && rightLCA) {
return root;
}
return (leftLCA != nullptr) ? leftLCA : rightLCA;
}5. Delete a node from a binary search tree.
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) {
return nullptr;
}
if (root->val > key) {
root->left = deleteNode(root->left, key);
} else if (root->val < key) {
root->right = deleteNode(root->right, key);
} else {
if (root->left == nullptr) {
TreeNode* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
TreeNode* temp = root->left;
delete root;
return temp;
}
TreeNode* temp = findMinNode(root->right);
root->val = temp->val;
root->right = deleteNode(root->right, temp->val);
}
return root;
}6. Find the depth of the deepest odd level leaf node.
int maxDepth(TreeNode* root, int depth) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr && depth % 2 != 0) {
return depth;
}
return max(maxDepth(root->left, depth + 1), maxDepth(root->right, depth + 1));
}
int deepestOddLevelLeaf(TreeNode* root) {
return maxDepth(root, 1);
}7. Find the maximum path sum in a binary tree.
int maxPathSum(TreeNode* root, int& maxSum) {
if (root == nullptr) {
return 0;
}
int leftSum = max(0, maxPathSum(root->left, maxSum));
int rightSum = max(0, maxPathSum(root->right, maxSum));
int currentSum = root->val + leftSum + rightSum;
maxSum = max(maxSum, currentSum);
return root->val + max(leftSum, rightSum);
}
int maxPathSum(TreeNode* root) {
int maxSum = INT_MIN;
maxPathSum(root, maxSum);
return maxSum;
}8. Print all nodes at a distance k from a given node.
void findKDistanceNodes(TreeNode* root, int k, vector<int>& result) {
if (root == nullptr) {
return;
}
if (k == 0) {
result.push_back(root->val);
return;
}
findKDistanceNodes(root->left, k - 1, result);
findKDistanceNodes(root->right, k - 1, result);
}
int findTargetNode(TreeNode* root, int target, int k, vector<int>& result) {
if (root == nullptr) {
return -1;
}
if (root->val == target) {
findKDistanceNodes(root, k, result);
return 0;
}
int leftDistance = findTargetNode(root->left, target, k, result);
if (leftDistance != -1) {
if (leftDistance + 1 == k) {
result.push_back(root->val);
} else {
findKDistanceNodes(root->right, k - leftDistance - 2, result);
}
return leftDistance + 1;
}
int rightDistance = findTargetNode(root->right, target, k, result);
if (rightDistance != -1) {
if (rightDistance + 1 == k) {
result.push_back(root->val);
} else {
findKDistanceNodes(root->left, k - rightDistance - 2, result);
}
return rightDistance + 1;
}
return -1;
}
vector<int> findNodesAtDistanceK(TreeNode* root, TreeNode* target, int k) {
vector<int> result;
findTargetNode(root, target->val, k, result);
return result;
}9. Convert a binary tree into its mirror tree.
TreeNode* mirrorTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* temp = root->left;
root->left = mirrorTree(root->right);
root->right = mirrorTree(temp);
return root;
}10. Check if a binary tree is a subtree of another binary tree.
bool isSameTree(TreeNode* s, TreeNode* t) {
if (s == nullptr && t == nullptr) {
return true;
}
if (s == nullptr || t == nullptr) {
return false;
}
return (s->val == t->val) && isSameTree(s->left, t->left) && isSameTree(s->right, t->right);
}
bool isSubtree(TreeNode* s, TreeNode* t) {
if (s == nullptr) {
return false;
}
return isSameTree(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
}11. Convert a binary tree into a doubly linked list.
class Node {
public:
int val;
Node* left;
Node* right;
Node(int value) : val(value), left(nullptr), right(nullptr) {}
};
Node* prev = nullptr;
void convertToDLL(Node* root, Node*& head) {
if (root == nullptr) {
return;
}
convertToDLL(root->left, head);
if (prev == nullptr) {
head = root;
} else {
root->left = prev;
prev->right = root;
}
prev = root;
convertToDLL(root->right, head);
}12. Clone a binary tree.
TreeNode* cloneTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* newRoot = new TreeNode(root->val);
newRoot->left = cloneTree(root->left);
newRoot->right = cloneTree(root->right);
return newRoot;
}13. Print the left view of a binary tree.
void printLeftView(TreeNode* root, int level, int& maxLevel) {
if (root == nullptr) {
return;
}
if (level > maxLevel) {
cout << root->val << " ";
maxLevel = level;
}
printLeftView(root->left, level + 1, maxLevel);
printLeftView(root->right, level + 1, maxLevel);
}
void leftView(TreeNode* root) {
int maxLevel = 0;
printLeftView(root, 1, maxLevel);
}14. Print the right view of a binary tree.
void printRightView(TreeNode* root, int level, int& maxLevel) {
if (root == nullptr) {
return;
}
if (level > maxLevel) {
cout << root->val << " ";
maxLevel = level;
}
printRightView(root->right, level + 1, maxLevel);
printRightView(root->left, level + 1, maxLevel);
}
void rightView(TreeNode* root) {
int maxLevel = 0;
printRightView(root, 1, maxLevel);
}15. Implement a Binary Search Tree iterator.
class BSTIterator {
public:
stack<TreeNode*> nodes;
BSTIterator(TreeNode* root) {
pushAll(root);
}
void pushAll(TreeNode* node) {
while (node != nullptr) {
nodes.push(node);
node = node->left;
}
}
int next() {
TreeNode* curr = nodes.top();
nodes.pop();
if (curr->right != nullptr) {
pushAll(curr->right);
}
return curr->val;
}
bool hasNext() {
return !nodes.empty();
}
};16. Serialize and deserialize a binary tree.
void serialize(TreeNode* root, stringstream& ss) {
if (root == nullptr) {
ss << "# ";
return;
}
ss << root->val << " ";
serialize(root->left, ss);
serialize(root->right, ss);
}
TreeNode* deserialize(stringstream& ss) {
string val;
ss >> val;
if (val == "#") {
return nullptr;
}
TreeNode* root = new TreeNode(stoi(val));
root->left = deserialize(ss);
root->right = deserialize(ss);
return root;
}17. Find the diameter of a binary tree.
int diameterOfBinaryTree(TreeNode* root) {
int diameter = 0;
depth(root, diameter);
return diameter;
}
int depth(TreeNode* node, int& diameter) {
if (node == nullptr) {
return 0;
}
int leftDepth = depth(node->left, diameter);
int rightDepth = depth(node->right, diameter);
diameter = max(diameter, leftDepth + rightDepth);
return max(leftDepth, rightDepth) + 1;
}18. Print the top view of a binary tree.
void topView(TreeNode* root) {
if (root == nullptr) {
return;
}
map<int, int> verticalMap;
queue<pair<TreeNode*, int>> q;
q.push({root, 0});
while (!q.empty()) {
TreeNode* node = q.front().first;
int hd = q.front().second;
q.pop();
if (verticalMap.find(hd) == verticalMap.end()) {
verticalMap[hd] = node->val;
}
if (node->left) {
q.push({node->left, hd - 1});
}
if (node->right) {
q.push({node->right, hd + 1});
}
}
for (auto it : verticalMap) {
cout << it.second << " ";
}
}19. Print the bottom view of a binary tree.
void bottomView(TreeNode* root) {
if (root == nullptr) {
return;
}
map<int, int> verticalMap;
queue<pair<TreeNode*, int>> q;
q.push({root, 0});
while (!q.empty()) {
TreeNode* node = q.front().first;
int hd = q.front().second;
q.pop();
verticalMap[hd] = node->val;
if (node->left) {
q.push({node->left, hd - 1});
}
if (node->right) {
q.push({node->right, hd + 1});
}
}
for (auto it : verticalMap) {
cout << it.second << " ";
}
}20. Check if a binary tree is a full binary tree.
bool isFullTree(TreeNode* root) {
if (root == nullptr) {
return true;
}
if (root->left == nullptr && root->right == nullptr) {
return true;
}
if (root->left && root->right) {
return isFullTree(root->left) && isFullTree(root->right);
}
return false;
}21. Check if a binary tree is a complete binary tree.
bool isCompleteTree(TreeNode* root) {
if (root == nullptr) {
return true;
}
queue<TreeNode*> q;
q.push(root);
bool end = false;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node == nullptr) {
end = true;
} else {
if (end) {
return false;
}
q.push(node->left);
q.push(node->right);
}
}
return true;
}22. Find the kth smallest element in a binary search tree.
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> s;
while (root || !s.empty()) {
while (root) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
if (--k == 0) {
return root->val;
}
root = root->right;
}
return -1; // kth element doesn't exist
}23. Implement an AVL Tree with insert, delete, and search functionality.
class AVLTree {
private:
struct TreeNode {
int val;
int height;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : val(value), height(1), left(nullptr), right(nullptr) {}
};
TreeNode* root;
int getHeight(TreeNode* node) {
if (node == nullptr) {
return 0;
}
return node->height;
}
int getBalance(TreeNode* node) {
if (node == nullptr) {
return 0;
}
return getHeight(node->left) - getHeight(node->right);
}
TreeNode* rightRotate(TreeNode* y) {
TreeNode* x = y->left;
TreeNode* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;
}
TreeNode* leftRotate(TreeNode* x) {
TreeNode* y = x->right;
TreeNode* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y;
}
TreeNode* insert(TreeNode* node, int val) {
if (node == nullptr) {
return new TreeNode(val);
}
if (val < node->val) {
node->left = insert(node->left, val);
} else if (val > node->val) {
node->right = insert(node->right, val);
} else {
return node; // Duplicate keys not allowed
}
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
int balance = getBalance(node);
// Left Left Case
if (balance > 1 && val < node->left->val) {
return rightRotate(node);
}
// Right Right Case
if (balance < -1 && val > node->right->val) {
return leftRotate(node);
}
// Left Right Case
if (balance > 1 && val > node->left->val) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && val < node->right->val) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
TreeNode* minValueNode(TreeNode* node) {
TreeNode* current = node;
while (current->left != nullptr) {
current = current->left;
}
return current;
}
TreeNode* deleteNode(TreeNode* node, int val) {
if (node == nullptr) {
return node;
}
if (val < node->val) {
node->left = deleteNode(node->left, val);
} else if (val > node->val) {
node->right = deleteNode(node->right, val);
} else {
if (node->left == nullptr || node->right == nullptr) {
TreeNode* temp = node->left ? node->left : node->right;
if (temp == nullptr)
{
temp = node;
node = nullptr;
} else {
*node = *temp;
}
delete temp;
} else {
TreeNode* temp = minValueNode(node->right);
node->val = temp->val;
node->right = deleteNode(node->right, temp->val);
}
}
if (node == nullptr) {
return node;
}
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
int balance = getBalance(node);
// Left Left Case
if (balance > 1 && getBalance(node->left) >= 0) {
return rightRotate(node);
}
// Left Right Case
if (balance > 1 && getBalance(node->left) < 0) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Right Case
if (balance < -1 && getBalance(node->right) <= 0) {
return leftRotate(node);
}
// Right Left Case
if (balance < -1 && getBalance(node->right) > 0) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
TreeNode* search(TreeNode* node, int val) {
if (node == nullptr || node->val == val) {
return node;
}
if (node->val < val) {
return search(node->right, val);
}
return search(node->left, val);
}
public:
AVLTree() : root(nullptr) {}
void insert(int val) {
root = insert(root, val);
}
void deleteNode(int val) {
root = deleteNode(root, val);
}
bool search(int val) {
return search(root, val) != nullptr;
}
};24. Merge two balanced binary search trees.
void inOrderTraversal(TreeNode* root, vector<int>& result) {
if (root == nullptr) {
return;
}
inOrderTraversal(root->left, result);
result.push_back(root->val);
inOrderTraversal(root->right, result);
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
vector<int> sorted1, sorted2;
inOrderTraversal(root1, sorted1);
inOrderTraversal(root2, sorted2);
vector<int> merged;
merge(sorted1.begin(), sorted1.end(), sorted2.begin(), sorted2.end(), back_inserter(merged));
return sortedArrayToBST(merged, 0, merged.size() - 1);
}25. Convert a sorted array to a balanced binary search tree.
TreeNode* sortedArrayToBST(vector<int>& nums, int left, int right) {
if (left > right) {
return nullptr;
}
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = sortedArrayToBST(nums, left, mid - 1);
root->right = sortedArrayToBST(nums, mid + 1, right);
return root;
}26. Implement a Trie (Prefix Tree).
class TrieNode {
public:
bool isEnd;
vector<TrieNode*> children;
TrieNode() : isEnd(false), children(26, nullptr) {}
};
class Trie {
private:
TrieNode* root;
public:
Trie() : root(new TrieNode()) {}
void insert(string word) {
TrieNode* node = root;
for (char ch : word) {
int index = ch - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEnd = true;
}
bool search(string word) {
TrieNode* node = root;
for (char ch : word) {
int index = ch - 'a';
if (!node->children[index]) {
return false;
}
node = node->children[index];
}
return node->isEnd;
}
bool startsWith(string prefix) {
TrieNode* node = root;
for (char ch : prefix) {
int index = ch - 'a';
if (!node->children[index]) {
return false;
}
node = node->children[index];
}
return true;
}
};27. Connect nodes at the same level in a binary tree.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}
};
Node* connect(Node* root) {
if (root == nullptr) {
return nullptr;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
Node* prev = nullptr;
for (int i = 0; i < size; i++) {
Node* curr = q.front();
q.pop();
if (prev != nullptr) {
prev->next = curr;
}
prev = curr;
if (curr->left) {
q.push(curr->left);
}
if (curr->right) {
q.push(curr->right);
}
}
}
return root;
}28. Find the longest leaf to leaf path in a binary tree.
int longestLeafToLeafPath(TreeNode* root, int& result) {
if (root == nullptr) {
return 0;
}
int left = longestLeafToLeafPath(root->left, result);
int right = longestLeafToLeafPath(root->right, result);
result = max(result, left + right + 1);
return max(left, right) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
int result = 0;
longestLeafToLeafPath(root, result);
return result - 1; // Return the number of edges instead of nodes
}29. Find the vertical sum in a given binary tree.
void verticalSumUtil(TreeNode* root, int hd, map<int, int>& verticalSum) {
if (root == nullptr) {
return;
}
verticalSum[hd] += root->val;
verticalSumUtil(root->left, hd - 1, verticalSum);
verticalSumUtil(root->right, hd + 1, verticalSum);
}
void verticalSum(TreeNode* root) {
map<int, int> verticalSum;
verticalSumUtil(root, 0, verticalSum);
for (auto it : verticalSum) {
cout << "Vertical sum at hd " << it.first << ": " << it.second << endl;
}
}30. Find the vertical traversal of a binary tree.
void verticalTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
map<int, vector<int>> verticalMap;
queue<pair<TreeNode*, int>> q;
q.push({root, 0});
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front().first;
int hd = q.front().second;
q.pop();
verticalMap[hd].push_back(node->val);
if (node->left) {
q.push({node->left, hd - 1});
}
if (node->right) {
q.push({node->right, hd + 1});
}
}
}
for (auto it : verticalMap) {
cout << "Vertical nodes at hd " << it.first << ": ";
for (int val : it.second) {
cout << val << " ";
}
cout << endl;
}
}31. Check if all leaves are at the same level in a binary tree.
bool isSameLevelLeaves(TreeNode* root) {
if (root == nullptr) {
return true;
}
queue<TreeNode*> q;
q.push(root);
int targetLevel = -1;
while (!q.empty()) {
int size = q.size();
bool hasLeaf = false;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left == nullptr && node->right == nullptr) {
if (targetLevel == -1) {
targetLevel = node->val;
} else if (node->val != targetLevel) {
return false;
}
hasLeaf = true;
}
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
if (hasLeaf && !q.empty()) {
return false; // There should be no more level after the first leaf level
}
}
return true;
}32. Find the maximum width of a binary tree.
int maxWidthOfBinaryTree(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int maxWidth = 1;
queue<pair<TreeNode*, int>> q;
q.push({root, 0});
while (!q.empty()) {
int size = q.size();
int leftmostIndex = q.front().second;
int rightmostIndex = q.front().second;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front().first;
int index = q.front().second;
q.pop();
rightmostIndex = index;
if (node->left) {
q.push({node->left, 2 * index});
}
if (node->right) {
q.push({node->right, 2 * index + 1});
}
}
int width = rightmostIndex - leftmostIndex + 1;
maxWidth = max(maxWidth, width);
}
return maxWidth;
}33. Print diagonal traversal of a binary tree.
void diagonalTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
while (node) {
cout << node->val << " ";
if (node->left) {
q.push(node->left);
}
node = node->right;
}
}
}34. Write a function to print boundary traversal of a binary tree.
void printLeftBoundary(TreeNode* root) {
if (root == nullptr) {
return;
}
if (root->left) {
cout << root->val << " ";
printLeftBoundary(root->left);
} else if (root->right) {
cout << root->val << " ";
printLeftBoundary(root->right);
}
}
void printRightBoundary(TreeNode* root) {
if (root == nullptr) {
return;
}
if (root->right) {
printRightBoundary(root->right);
cout << root->val << " ";
} else if (root->left) {
printRightBoundary(root->left);
cout << root->val << " ";
}
}
void printLeaves(TreeNode* root) {
if (root == nullptr) {
return;
}
printLeaves(root->left);
if (!root->left && !root->right) {
cout << root->val << " ";
}
printLeaves(root->right);
}
void boundaryTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
printLeftBoundary(root->left);
printLeaves(root->left);
printLeaves(root->right);
printRightBoundary(root->right);
}35. Write a function to find the Inorder predecessor and successor in a Binary Search Tree.
void findPredecessorAndSuccessor(TreeNode* root, TreeNode*& predecessor, TreeNode*& successor, int key) {
if (root == nullptr) {
return;
}
if (root->val == key) {
if (root->left) {
TreeNode* temp = root->left;
while (temp->right) {
temp = temp->right;
}
predecessor = temp;
}
if (root->right) {
TreeNode* temp = root->right;
while (temp->left) {
temp = temp->left;
}
successor = temp;
}
return;
}
if (root->val > key) {
successor = root;
findPredecessorAndSuccessor(root->left, predecessor, successor, key);
} else {
predecessor = root;
findPredecessorAndSuccessor(root->right, predecessor, successor, key);
}
}36. Write a function to check if a given array can represent the Preorder Traversal of a Binary Search Tree.
bool canRepresentBST(vector<int>& preorder) {
int root = INT_MIN;
stack<int> s;
for (int value : preorder) {
if (value < root) {
return false;
}
while (!s.empty() && value > s.top()) {
root = s.top();
s.pop();
}
s.push(value);
}
return true;
}37. Implement a Segment Tree with the sum of the given range.
class SegmentTree {
private:
vector<int> tree;
int n;
void build(vector<int>& nums, int node, int start, int end) {
if (start == end) {
tree[node] = nums[start];
} else {
int mid = start + (end - start) / 2;
build(nums, 2 * node + 1, start, mid);
build(nums, 2 * node + 2, mid + 1, end);
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
void update(int node, int start, int end, int index, int val) {
if (start == end) {
tree[node] = val;
} else {
int mid = start + (end - start) / 2;
if (index <= mid) {
update(2 * node + 1, start, mid, index, val);
} else {
update(2 * node + 2, mid + 1, end, index, val);
}
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
int query(int node, int start, int end, int left, int right) {
if (start > right || end < left) {
return 0;
}
if (start >= left && end <= right) {
return tree[node];
}
int mid = start + (end - start) / 2;
int leftSum = query(2 * node + 1, start, mid, left, right);
int rightSum = query(2 * node + 2, mid + 1, end, left, right);
return leftSum + rightSum;
}
public:
SegmentTree(vector<int>& nums) {
n = nums.size();
tree.resize(4 * n);
build(nums, 0, 0, n - 1);
}
void update(int index, int val) {
update(0, 0, n - 1, index, val);
}
int query(int left, int right) {
return query(0, 0, n - 1, left, right);
}
};38. Implement a Fenwick Tree or Binary Indexed Tree.
class FenwickTree {
private:
vector<int> BIT;
public:
FenwickTree(int n) : BIT(n + 1) {}
void update(int index, int val) {
index++;
while (index < BIT.size()) {
BIT[index] += val;
index += index & -index;
}
}
int query(int index) {
index++;
int sum = 0;
while (index > 0) {
sum += BIT[index];
index -= index & -index;
}
return sum;
}
int query(int left, int right) {
return query(right) - query(left - 1);
}
};39. Write a function to convert a Binary Tree to Binary Search Tree.
void inOrderTraversal(TreeNode* root, vector<int>& inorder) {
if (root == nullptr) {
return;
}
inOrderTraversal(root->left, inorder);
inorder.push_back(root->val);
inOrderTraversal(root->right, inorder);
}
TreeNode* sortedArrayToBST(vector<int>& inorder, int left, int right) {
if (left > right) {
return nullptr;
}
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(inorder[mid]);
root->left = sortedArrayToBST(inorder, left, mid - 1);
root->right = sortedArrayToBST(inorder, mid + 1, right);
return root;
}
TreeNode* binaryTreeToBST(TreeNode* root) {
vector<int> inorder;
inOrderTraversal(root,
inorder);
return sortedArrayToBST(inorder, 0, inorder.size() - 1);
}40. Write a function to construct all possible unique BSTs for keys 1 to N.
vector<TreeNode*> generateTrees(int start, int end) {
vector<TreeNode*> result;
if (start > end) {
result.push_back(nullptr);
return result;
}
for (int i = start; i <= end; i++) {
vector<TreeNode*> leftSubtrees = generateTrees(start, i - 1);
vector<TreeNode*> rightSubtrees = generateTrees(i + 1, end);
for (TreeNode* left : leftSubtrees) {
for (TreeNode* right : rightSubtrees) {
TreeNode* root = new TreeNode(i);
root->left = left;
root->right = right;
result.push_back(root);
}
}
}
return result;
}
vector<TreeNode*> generateUniqueBSTs(int n) {
if (n == 0) {
return {};
}
return generateTrees(1, n);
}41. Implement a B-Tree.
const int MIN_KEYS = 2;
const int MAX_KEYS = 4;
class BTreeNode {
private:
int keys[MAX_KEYS];
BTreeNode* children[MAX_KEYS + 1];
int numKeys;
bool isLeaf;
public:
BTreeNode(bool leaf = true) : numKeys(0), isLeaf(leaf) {}
int getKey(int index) const {
return keys[index];
}
BTreeNode* getChild(int index) const {
return children[index];
}
void setKey(int index, int key) {
keys[index] = key;
}
void setChild(int index, BTreeNode* child) {
children[index] = child;
}
int getNumKeys() const {
return numKeys;
}
void setNumKeys(int num) {
numKeys = num;
}
bool isFull() const {
return numKeys == MAX_KEYS;
}
bool isLeafNode() const {
return isLeaf;
}
};
class BTree {
private:
BTreeNode* root;
void splitChild(BTreeNode* parent, int index) {
BTreeNode* child = parent->getChild(index);
BTreeNode* newNode = new BTreeNode(child->isLeafNode());
int midIndex = MAX_KEYS / 2;
for (int i = midIndex + 1; i < MAX_KEYS; i++) {
newNode->setKey(i - midIndex - 1, child->getKey(i));
newNode->setChild(i - midIndex - 1, child->getChild(i));
}
newNode->setNumKeys(MAX_KEYS - midIndex - 1);
child->setNumKeys(midIndex);
for (int i = parent->getNumKeys(); i > index; i--) {
parent->setKey(i, parent->getKey(i - 1));
}
parent->setKey(index, child->getKey(midIndex));
parent->setChild(index + 1, newNode);
parent->setNumKeys(parent->getNumKeys() + 1);
}
void insertNonFull(BTreeNode* node, int key) {
int i = node->getNumKeys() - 1;
if (node->isLeafNode()) {
while (i >= 0 && key < node->getKey(i)) {
node->setKey(i + 1, node->getKey(i));
i--;
}
node->setKey(i + 1, key);
node->setNumKeys(node->getNumKeys() + 1);
} else {
while (i >= 0 && key < node->getKey(i)) {
i--;
}
i++;
BTreeNode* child = node->getChild(i);
if (child->isFull()) {
splitChild(node, i);
if (key > node->getKey(i)) {
i++;
child = node->getChild(i);
}
}
insertNonFull(child, key);
}
}
BTreeNode* searchNode(BTreeNode* node, int key) const {
int i = 0;
while (i < node->getNumKeys() && key > node->getKey(i)) {
i++;
}
if (i < node->getNumKeys() && key == node->getKey(i)) {
return node;
}
if (node->isLeafNode()) {
return nullptr;
}
return searchNode(node->getChild(i), key);
}
public:
BTree() : root(new BTreeNode()) {}
void insert(int key) {
if (root->isFull()) {
BTreeNode* newNode = new BTreeNode(false);
newNode->setChild(0, root);
splitChild(newNode, 0);
root = newNode;
}
insertNonFull(root, key);
}
bool search(int key) const {
return searchNode(root, key) != nullptr;
}
};42. Write a function to determine if two N-ary trees are identical.
class Node {
public:
int val;
vector<Node*> children;
Node(int _val) : val(_val) {}
};
bool areIdentical(Node* root1, Node* root2) {
if (root1 == nullptr && root2 == nullptr) {
return true;
}
if (root1 == nullptr || root2 == nullptr) {
return false;
}
if (root1->val != root2->val) {
return false;
}
if (root1->children.size() != root2->children.size()) {
return false;
}
for (int i = 0; i < root1->children.size(); i++) {
if (!areIdentical(root1->children[i], root2->children[i])) {
return false;
}
}
return true;
}43. Write a function to check if a binary tree is a perfect binary tree.
bool isPerfectBinaryTree(TreeNode* root) {
if (root == nullptr) {
return true;
}
int leftHeight = 0;
TreeNode* left = root;
while (left != nullptr) {
leftHeight++;
left = left->left;
}
int rightHeight = 0;
TreeNode* right = root;
while (right != nullptr) {
rightHeight++;
right = right->right;
}
return leftHeight == rightHeight;
}44. Implement a function to perform a level order traversal on a binary tree.
vector<vector<int>> levelOrderTraversal(TreeNode* root) {
vector<vector<int>> result;
if (root == nullptr) {
return result;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
vector<int> levelNodes;
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
levelNodes.push_back(node->val);
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
result.push_back(levelNodes);
}
return result;
}45. Write a function to find the longest consecutive sequence in a binary tree.
void findLongestConsecutive(TreeNode* root, int currentLength, int expectedValue, int& maxLength) {
if (root == nullptr) {
return;
}
if (root->val == expectedValue) {
currentLength++;
} else {
currentLength = 1;
}
maxLength = max(maxLength, currentLength);
findLongestConsecutive(root->left, currentLength, root->val + 1, maxLength);
findLongestConsecutive(root->right, currentLength, root->val + 1, maxLength);
}
int longestConsecutive(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int maxLength = 0;
findLongestConsecutive(root, 0, root->val, maxLength);
return maxLength;
}46. Write a function to count the number of uni-value subtrees in a binary tree.
bool isUniValue(TreeNode* root, int& count) {
if (root == nullptr) {
return true;
}
bool leftUni = isUniValue(root->left, count);
bool rightUni = isUniValue(root->right, count);
if (leftUni && rightUni) {
if ((root->left == nullptr || root->left->val == root->val) &&
(root->right == nullptr || root->right->val == root->val)) {
count++;
return true;
}
}
return false;
}
int countUniValueSubtrees(TreeNode* root) {
int count = 0;
isUniValue(root, count);
return count;
}47. Write a function to print nodes in a binary tree by diagonal traversal.
void diagonalTraversal(TreeNode* root, int level, map<int, vector<int>>& diagonalMap) {
if (root == nullptr) {
return;
}
diagonalMap[level].push_back(root->val);
diagonalTraversal(root->left, level + 1, diagonalMap);
diagonalTraversal(root->right, level, diagonalMap);
}
vector<vector<int>> diagonalTraversal(TreeNode* root) {
vector<vector<int>> result;
map<int, vector<int>> diagonalMap;
diagonalTraversal(root, 0, diagonalMap);
for (auto it : diagonalMap) {
result.push_back(it.second);
}
return result;
}48. Write a function to print the zigzag traversal of a binary tree.
vector<vector<int>> zigzagTraversal(TreeNode* root) {
vector<vector<int>> result;
if (root == nullptr) {
return result;
}
queue<TreeNode*> q;
q.push(root);
bool leftToRight = true;
while (!q.empty()) {
int levelSize = q.size();
vector<int> levelNodes;
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
if (leftToRight) {
levelNodes.push_back(node->val);
} else {
levelNodes.insert(levelNodes.begin(), node->val);
}
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
result.push_back(levelNodes);
leftToRight = !leftToRight;
}
return result;
}49. Write a function to check if a given binary tree is a sum tree or not.
bool isLeaf(TreeNode* root) {
return root && !root->left && !root->right;
}
bool isSumTree(TreeNode* root) {
if (root == nullptr || isLeaf(root)) {
return true;
}
int leftSum = 0;
int rightSum = 0;
if (isSumTree(root->left) && isSumTree(root->right)) {
if (root->left == nullptr) {
leftSum = 0;
} else if (isLeaf(root->left)) {
leftSum = root->left->val;
} else {
leftSum = 2 * root->left->val;
}
if (root->right == nullptr) {
rightSum = 0;
} else if (isLeaf(root->right)) {
rightSum = root->right->val;
} else {
rightSum = 2 * root->right->val;
}
return root->val == leftSum + rightSum;
}
return false;
}50. Write a function to find the maximum width of a binary tree.
int maxWidthOfBinaryTree(TreeNode* root) {
if (root ==
nullptr) {
return 0;
}
queue<TreeNode*> q;
q.push(root);
int maxWidth = 0;
while (!q.empty()) {
int levelSize = q.size();
maxWidth = max(maxWidth, levelSize);
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}
return maxWidth;
}MCQ Questions
1. What is a tree data structure?
a) A linear data structure
b) A hierarchical data structure
c) A stack-based data structure
d) A queue-based data structure
Answer: b) A hierarchical data structure
2. What is a binary tree?
a) A tree with two children for each node
b) A tree with three children for each node
c) A tree with four children for each node
d) A tree with any number of children for each node
Answer: a) A tree with two children for each node
3. In a binary tree, what is a leaf node?
a) The root node
b) A node with only one child
c) A node with no children
d) A node with two children
Answer: c) A node with no children
4. What is the height of a tree?
a) The number of nodes in the tree
b) The length of the longest path from the root to a leaf node
c) The number of levels in the tree
d) The depth of the root node
Answer: c) The number of levels in the tree
5. Which traversal visits the nodes in the order: left subtree, root, right subtree?
a) In-order traversal
b) Pre-order traversal
c) Post-order traversal
d) Level-order traversal
Answer: a) In-order traversal
6. Which traversal visits the nodes in the order: root, left subtree, right subtree?
a) In-order traversal
b) Pre-order traversal
c) Post-order traversal
d) Level-order traversal
Answer: b) Pre-order traversal
7. Which traversal visits the nodes in the order: left subtree, right subtree, root?
a) In-order traversal
b) Pre-order traversal
c) Post-order traversal
d) Level-order traversal
Answer: c) Post-order traversal
8. Which traversal is best suited for creating a copy of a binary tree?
a) In-order traversal
b) Pre-order traversal
c) Post-order traversal
d) Level-order traversal
Answer: b) Pre-order traversal
9. What is the maximum number of nodes at level L in a binary tree?
a) L
b) 2^L
c) 2^(L+1) – 1
d) 2^(L-1)
Answer: b) 2^L
10. Which binary tree traversal can be used to convert a binary search tree into a sorted array?
a) In-order traversal
b) Pre-order traversal
c) Post-order traversal
d) Level-order traversal
Answer: a) In-order traversal
11. What is a binary search tree (BST)?
a) A binary tree with any number of children for each node
b) A binary tree with exactly two children for each node
c) A binary tree where each node has a value greater than its left child and less than its right child
d) A binary tree where each node has a value greater than or equal to its left child and less than or equal to its right child
Answer: c) A binary tree where each node has a value greater than its left child and less than its right child
12. What is the time complexity for finding an element in a binary search tree (BST)?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: b) O(log n)
13. What is the time complexity for inserting an element in a binary search tree (BST)?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: b) O(log n)
14. What is the time complexity for deleting an element in a binary search tree (BST)?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: b) O(log n)
15. What is an AVL tree?
a) A self-balancing binary search tree
b) A tree with any number of children for each node
c) A tree with exactly two children for each node
d) A tree where each node has a value greater than its left child and less than its right child
Answer: a) A self-balancing binary search tree
16. What is a red-black tree?
a) A self-balancing binary search tree with additional constraints on node colors
b) A tree with any number of children for each node
c) A tree with exactly two children for each node
d) A tree where each node has a value greater than its left child and less than its right child
Answer: a) A self-balancing binary search tree with additional constraints on node colors
17. Which data structure is used for implementing a priority queue?
a) Queue
b) Stack
c) Binary heap
d) AVL tree
Answer: c) Binary heap
18. What is a trie data structure used for?
a) Storing elements in sorted order
b) Implementing priority queues
c) Efficiently storing and searching for strings with common prefixes
d) Storing elements in a self-balancing binary search tree
Answer: c) Efficiently storing and searching for strings with common prefixes
19. Which traversal can be used to find the height of a binary tree?
a) In-order traversal
b) Pre-order traversal
c) Post-order traversal
d) Level-order traversal
Answer: d) Level-order traversal
20. What is the time complexity of searching for an element in a trie?
a) O(1)
b) O(log n)
c) O(n)
d) O(m), where m is the length of the string
Answer: d) O(m), where m is the length of the string
21. What is the time complexity of inserting a word of length m in a trie with n total words?
a) O(1)
b) O(log n)
c) O(n)
d) O(m)
Answer: d) O(m)
22. Which data structure is used for implementing Huffman coding, a popular data compression algorithm?
a) Linked list
b) Stack
c) Priority queue
d) Queue
Answer: c) Priority queue
23. What is a B-tree data structure used for?
a) Storing elements in sorted order
b) Implementing priority queues
c) Efficiently storing and searching for strings with common prefixes
d) Storing elements in a self-balancing binary search tree
Answer: a) Storing elements in sorted order
24. What is an n-ary tree?
a) A tree with two children for each node
b) A tree with exactly three children for each node
c) A tree with any number of children, where n can be any positive integer
d) A tree with exactly n children for each node
Answer: c) A tree with any number of children, where n can be any positive integer
25. Which data structure is used for implementing the undo-redo feature in text editors?
a) Stack
b) Queue
c) Linked list
d) Trie
Answer: a) Stack
26. What is the time complexity of finding the minimum element in a binary search tree (BST)?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: b) O(log n)
27. What is a full binary tree?
a) A binary tree with all nodes having two children
b) A binary tree with only one child for each node
c) A binary tree with no child nodes
d) A binary tree with exactly one child for each node
Answer: a) A binary tree with all nodes having two children
28. Which data structure is used for implementing the call stack in programming languages?
a) Queue
b) Stack
c) Linked list
d) Trie
Answer: b) Stack
29. What is an AVL tree height-balancing property?
a) The height of the left subtree is equal to the height of the right subtree for each node
b) The height of the left subtree is less than or equal to the height of the right subtree for each node
c) The height of the left subtree is greater than or equal to the height of the right subtree for each node
d) The height of the left subtree is at most double the height of the right subtree for each node
Answer: a) The height of the left subtree is equal to the height of the right subtree for each node
30. Which data structure is used for implementing the back button in web browsers?
a) Queue
b) Stack
c) Linked list
d) Trie
Answer: b) Stack
