When deleting a node with two children in a BST, what is the standard approach to maintain the BST property?
Replace the node's value with the smallest value from its right subtree and recursively delete the node with the smallest value.
Replace the node's value with the largest value from its left subtree and recursively delete the node with the largest value.
Remove the node and connect its children directly to its parent.
Any of the above options can be used.
What is the key difference between single threading and double threading in a Threaded Binary Tree?
Single threading is used for BSTs, while double threading is for general binary trees.
There is no practical difference; they are conceptually the same.
Single threading allows only inorder traversal, while double threading enables preorder traversal as well.
Single threading only uses right null pointers, while double threading uses both left and right.
When constructing a Segment Tree for a given array, what information is typically stored in each node of the Segment Tree?
The minimum value within the corresponding subarray of the original array.
A statistical measure (like mean or median) of the corresponding subarray.
The sum of all elements in the corresponding subarray of the original array.
It depends on the specific application and the type of queries the Segment Tree is designed to handle.
A certain algorithm requires a binary tree where all operations (insertion, deletion, search) must be guaranteed to be O(log n) in the worst case. Which type of tree is MOST suitable for this scenario?
Full Binary Tree
Perfect Binary Tree
Balanced Binary Tree
Complete Binary Tree
Which of the following real-world scenarios would be well-suited for using a Segment Tree data structure?
Implementing an undo/redo functionality in a text editor.
Finding the shortest path between two nodes in a weighted graph.
All of the above.
Storing and querying historical stock prices for a particular company.
Consider a Binary Search Tree (BST). What is the time complexity of finding the LCA of two nodes in the BEST-CASE scenario?
O(n)
O(log n)
O(1)
O(n log n)
You are given a binary tree where nodes have an additional pointer 'next'. This 'next' pointer is initially null. Design an algorithm to populate each next pointer to point to its right sibling. If there is no right sibling, the next pointer should remain null. Can this be done efficiently without using recursion?
It can only be done iteratively if the tree is a complete binary tree.
No, recursion is always required to connect nodes at different levels.
Yes, this can be done iteratively using Level Order Traversal (BFS).
It's impossible to achieve this without modifying the tree structure.
Why are rotations in AVL trees considered to be more complex than in Red-Black trees?
Red-Black trees don't require rotations.
AVL trees have more types of rotations (left, right, left-right, right-left).
AVL trees have stricter balance requirements, leading to more cases to handle during rotations.
AVL trees require more rotations to maintain balance.
Consider a Segment Tree designed to handle range sum queries. An update operation is performed on a single element of the original array. How many nodes in the Segment Tree, on average, need to be updated to reflect this change?
O(√n)
In a binary tree, you need to find the rightmost node at the deepest level. If multiple nodes share the maximum depth and are furthest to the right, find any one. Which traversal is most suitable?
Level Order Traversal
Depth-First Traversal (Postorder)
Depth-First Traversal (Preorder)
Depth-First Traversal (Inorder)