GATE Exam > GATE Notes > Binary Search Tree (BST)
Binary Search Tree (BST) - GATE PDF Download
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.I. 81, 537, 102, 439, 285, 376, 305II. 52, 97, 121, 195, 242, 381, 472III. 142, 248, 520, 386, 345, 270, 307IV. 550, 149, 507, 395, 463, 402, 270Q.Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?a)II and III onlyb)I and III onlyc)III and IV onlyd)III onlyCorrect answer is option 'D'. Can you explain this answer?
Ref: https://edurev.in/question/499405/A-Binary-Search-Tree-BST-stores-values-in-the-range37-to-573-Consider-the-following-sequence-of-k
Key to be searched 273:
- I) 81, 537, 102, 439, 285, 376, 305 is not correct
We cannot go to 376 from 285 as 273 is smaller than 285. - II) 52, 97, 121, 195, 242, 381, 472 is not correct.
We cannot go to 472 from 381 as 273 is smaller than 381. - III) 142, 248, 520, 386, 345, 270, 307 is correct
- 550, 149, 507, 395, 463, 402, 270 is not correct.
We cannot go to 463 from 395 in search of 273
FAQs on Binary Search Tree (BST) - GATE
| 1. What is a Binary Search Tree (BST)? |  |
Ans. A Binary Search Tree (BST) is a type of binary tree data structure in which each node has a key greater than the keys in its left subtree and less than the keys in its right subtree. It allows efficient searching, insertion, and deletion operations with an average time complexity of O(log n), where n is the number of nodes in the tree.
| 2. How does the search operation work in a Binary Search Tree (BST)? | |
Ans. To search for a specific key in a Binary Search Tree (BST), we start from the root node and compare the key with the current node's key. If the key is equal to the current node's key, we have found the desired element. If the key is less than the current node's key, we move to its left subtree. If the key is greater, we move to its right subtree. We repeat this process until we find the desired key or reach a leaf node (null), indicating that the key is not present in the tree.
| 3. How are elements inserted into a Binary Search Tree (BST)? | |
Ans. To insert an element into a Binary Search Tree (BST), we compare the key of the new element with the keys of existing nodes starting from the root. If the key is less than the current node's key, we move to its left subtree. If the key is greater, we move to its right subtree. We repeat this process until we reach a leaf node (null). At this point, we create a new node with the given key and attach it as a child to the appropriate position in the tree.
| 4. What is the time complexity of the insertion operation in a Binary Search Tree (BST)? | |
Ans. The time complexity of the insertion operation in a Binary Search Tree (BST) depends on the height of the tree. In the average case, when the tree is balanced, the time complexity is O(log n), where n is the number of nodes in the tree. However, in the worst case scenario, when the tree is skewed (all nodes have only left or right children), the time complexity can be O(n), where n is the number of nodes.
| 5. How can we delete a node from a Binary Search Tree (BST)? | |
Ans. To delete a node from a Binary Search Tree (BST), we first search for the node to be deleted. Once the node is found, there are three possible cases:
1. If the node has no children, we simply remove it by updating its parent's reference to null.
2. If the node has one child, we replace the node with its child by updating the appropriate reference in its parent.
3. If the node has two children, we find the node with the minimum key in its right subtree (or the maximum key in its left subtree), swap the keys of the two nodes, and then delete the node with the minimum (or maximum) key from the right (or left) subtree, which reduces the problem to one of the previous two cases.
The time complexity of the deletion operation in a Binary Search Tree (BST) is also dependent on the tree's height and can be O(log n) in the average case and O(n) in the worst case.
Related Exams
About this Document
Jan 16, 2025
Last updated
Document Description: Binary Search Tree (BST) for GATE 2025 is part of GATE preparation. The notes and questions for Binary Search Tree (BST) have been prepared according to the GATE exam syllabus. Information about Binary Search Tree (BST) covers topics like and Binary Search Tree (BST) Example, for GATE 2025 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for Binary Search Tree (BST).
Description
Full syllabus notes, lecture & questions for Binary Search Tree (BST) - GATE - GATE | Plus excerises question with solution to help you revise complete syllabus | Best notes, free PDF download
Information about Binary Search Tree (BST)
In this doc you can find the meaning of Binary Search Tree (BST) defined & explained in the simplest way possible.
Besides explaining types of Binary Search Tree (BST) theory,
EduRev gives you an ample number of questions to practice Binary Search Tree (BST) tests, examples and also practice GATE tests.
Related Searches
Viva Questions
,Free
,Objective type Questions
,study material
,Binary Search Tree (BST) - GATE
,Sample Paper
,MCQs
,video lectures
,Extra Questions
,shortcuts and tricks
,Previous Year Questions with Solutions
,practice quizzes
,Important questions
,mock tests for examination
,Binary Search Tree (BST) - GATE
,ppt
,Summary
,past year papers
,Semester Notes
,Exam
,Binary Search Tree (BST) - GATE
;
Additional Information about Binary Search Tree (BST) for GATE Preparation
Binary Search Tree (BST) Free PDF Download
The Binary Search Tree (BST) is an invaluable resource that delves deep into the core of the GATE exam.
These study notes are curated by experts and cover all the essential topics and concepts, making your preparation more efficient and effective.
With the help of these notes, you can grasp complex subjects quickly, revise important points easily,
and reinforce your understanding of key concepts. The study notes are presented in a concise and easy-to-understand manner,
allowing you to optimize your learning process. Whether you're looking for best-recommended books, sample papers, study material,
or toppers' notes, this PDF has got you covered. Download the Binary Search Tree (BST) now and kickstart your journey towards success in the GATE exam.
Importance of Binary Search Tree (BST)
The importance of Binary Search Tree (BST) cannot be overstated, especially for GATE aspirants.
This document holds the key to success in the GATE exam.
It offers a detailed understanding of the concept, providing invaluable insights into the topic.
By knowing the concepts well in advance, students can plan their preparation effectively.
Utilize this indispensable guide for a well-rounded preparation and achieve your desired results.
Binary Search Tree (BST) Notes
Binary Search Tree (BST) Notes offer in-depth insights into the specific topic to help you master it with ease.
This comprehensive document covers all aspects related to Binary Search Tree (BST).
It includes detailed information about the exam syllabus, recommended books, and study materials for a well-rounded preparation.
Practice papers and question papers enable you to assess your progress effectively.
Additionally, the paper analysis provides valuable tips for tackling the exam strategically.
Access to Toppers' notes gives you an edge in understanding complex concepts.
Whether you're a beginner or aiming for advanced proficiency, Binary Search Tree (BST) Notes on EduRev are your ultimate resource for success.
Binary Search Tree (BST) GATE Questions
The "Binary Search Tree (BST) GATE Questions" guide is a valuable resource for all aspiring students preparing for the
GATE exam. It focuses on providing a wide range of practice questions to help students gauge
their understanding of the exam topics. These questions cover the entire syllabus, ensuring comprehensive preparation.
The guide includes previous years' question papers for students to familiarize themselves with the exam's format and difficulty level.
Additionally, it offers subject-specific question banks, allowing students to focus on weak areas and improve their performance.
Study Binary Search Tree (BST) on the App
Students of GATE can study Binary Search Tree (BST) alongwith tests & analysis from the EduRev app,
which will help them while preparing for their exam. Apart from the Binary Search Tree (BST),
students can also utilize the EduRev App for other study materials such as previous year question papers, syllabus, important questions, etc.
The EduRev App will make your learning easier as you can access it from anywhere you want.
The content of Binary Search Tree (BST) is prepared as per the latest GATE syllabus.
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup