1 hour
The experiment features a series of modules with video lectures, hands-on practice exercises and quizzes for self analysis.
In this experiment, we will learn the following:
Module | Weightage | Expectation |
---|---|---|
Pre-test | 15% | Solve All Questions |
2-3 Basics | 25% | Understand the 2-3 Tree basics |
Operations | 35% | Understand the 2-3 Tree Algorithm |
Post-test | 25% | Solve all Questions |
10 minutes
Pretest includes questions on
Q1. Which of the following statements are correct about a binary tree?
(A) A node in a binary tree can have exactly two children
(B) A node in a binary tree can have atmost two children
(C) A node in a binary tree can have two or more children
(D) A node in a binary tree can have two or more children
A node in a binary tree, by definition, can have atmost two children.
Q2. Node values in a binary tree always appear in a sorted order from root to leaf, going left to right at each level.
(A) True
(B) False
There is no specific order in which keys are stored in a binary tree.
Q3. Which of the following is TRUE about the leaf nodes of a binary tree?
(A) Leaf nodes in a binary tree have no children
(B) Atleast one leaf node in a binary tree has two chidren
(C) Leaf nodes in a binary tree are allowed to have more than two children
(D) Leaf nodes in a binary tree may or may not have child nodes
Leaf nodes in a binary tree have no children, and this is the reason why they are called "leaf". Leaf nodes appear at the last level of the tree.
Q4. In a binary search tree all nodes in the left subtree are __________.
(A) SMALLER than the root
(B) GREATER than the root
(C) EQUAL to the root
All nodes in the left subtree of the root in a binary search tree are smaller than the root.
Q5. What is the worst case height possible in a binary search tree? Let N be the number of nodes in the tree.
(A) O(log N)
(B) O(N)
(C) O(1)
(D) None of the above
A BST need not be balanced and therefore, the worst case height possible is O(N), where N is the number of nodes in the tree.
15 minutes
Welcome to this module on tree 2-3 trees! Take a look at what you will go through in the module.
Video introduction to 2-3 tree experiment should be displayed here!
2–3 tree is a perfectly balanced binary search tree. It is called a 2-3 tree because each internal node has either 2 or 3 children. In 2-3 tree, every path from root to leaf has the same length and the data structure guarantees worst case O(log n) time complexity for search and insert operations.
There are three types of nodes in a 2-3 tree
2-3 tree has the following properties:
Q1. Which of the following is true?
(A) Data in a 2-3 tree is stored in unsorted manner
(B) Data in a 2-3 tree is stored in a sorted manner
(C) There is no ordering among data items in a 2-3 tree
(D) Only leaf nodes have sorted data items
Data items in a 2-3 tree are stored in a sorted manner. The left subtree has data items smaller than the root, the middle subtree has data item greater than root and smaller than right subtree and the right subtree has data items greater than left and middle subtree.
Q2. Which of the following is true?
(A) Leaf nodes in a 2-3 tree can be at any level
(B) Leaf nodes in a 2-3 tree can be only at odd levels
(C) All leaf nodes in a 2-3 have the same level
(D) None of the above
An important property of 2-3 is that all leaf nodes have the same level.
Q3. Which of the following best describes a 2-node?
(A) A 2-node has one data item and two children
(B) A 2-node has two data items and two children
(C) A 2-node has one data item and one child
(D) None of the above
By definition, a 2-node has one data item and two children.
Q4. Which of the following best describes a 3-node?
(A) A 3-node has one data item and two children
(B) A 3-node has two data items and three children
(C) A 3-node has one data item and one child
(D) None of the above
By definition, A 3-node has two data items and three children.
30 minutes
Welcome to this module on operations on 2-3 tree! Take a look at what you will go through in this module.
2-3 Search Video should be displayed here!
Searching for an item in a 2–3 tree is similar to searching for an item in a binary search tree. Since the data elements in each node are ordered, a search function will be directed to the correct subtree and eventually to the correct node which contains the item.
2-3 Insertion Video should be displayed here!
Insertion in a 2-3 tree is very different from a Binary Search Tree as in a 2-3 tree, a node can have one data item (2-Node) or two data items (3-Node). At first, we search for the correct position of the new data element to be inserted into the tree. Once, we have found the postion of the new data element, one of the two conditions arise:
2-3 Deletion Video should be displayed here!
10 minutes
Post-test includes questions on
Q1. Which of the following statements are correct about a 2-3 tree?
(A) A 2-3 tree has either 2 keys or 3 keys in every node
(B) A 2-3 has two types of nodes, namely 2-node and 3-node
(C) A node in a 2-3 tree can have only only one child
(D) A node in a 2-3 tree can have more than one root
By definition, a 2-3 tree can have 2-node and 3-node.
Q2. Key values in the nodes of a 2-3 tree always appear sorted from top to bottom and left to right in the tree.
(A) True
(B) False
Keys in a 2-3 tree are always sorted.
Q3. Keys in a 2-3 tree are always sorted when __________.
(A) All leaves in a 2-3 tree are at the same level
(B) Atleast one leaf node in a 2-3 tree has two chidren
(C) Leaf nodes in a 2-3 tree are allowed to have more than two children
(D) Leaf nodes in a 2-3 tree may or may not have child nodes
Leaf nodes in a 2-3 tree are at the same level
Q4. Which of the following is correct about a 2-node?
(A) A two node has only one child
(B) A two node has one data element and two children
(C) A two node has one data element and two children
A two node has one data element and two children.
Q5. What is the time complexity of search in a 2-3 tree?
(A) O(log N)
(B) O(N)
(C) O(1)
(D) None of the above
A 2-3 is a balanced tree so the time complexity of search is O(log N).
You can explore more about tree traversal through following resources: