🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
A Binary Search Tree (BST) is a binary tree where each node has a comparable value, and the left subtree of a node contains only nodes with values less than the node's value, while the right subtree only nodes with values greater than the node's value. This property ensures that operations like insert, delete, and find can be performed efficiently.
2. Implementation Steps
1. Define a Node class to represent individual nodes in the BST.
2. Create a BinarySearchTree class that will provide methods for common operations.
3. Implement methods such as insert, search, delete, findMin, findMax, inOrderTraversal, preOrderTraversal, and postOrderTraversal.
3. Implementation in Kotlin Programming
// Define the Node class
class Node(var data: Int) {
var left: Node? = null
var right: Node? = null
}
class BinarySearchTree {
var root: Node? = null
// Insert data into the BST
fun insert(value: Int) {
root = insertRecursive(root, value)
}
private fun insertRecursive(current: Node?, value: Int): Node {
if (current == null) {
return Node(value)
}
if (value < current.data) {
current.left = insertRecursive(current.left, value)
} else if (value > current.data) {
current.right = insertRecursive(current.right, value)
}
return current
}
// Search for a value in the tree
fun search(value: Int): Boolean {
return searchRecursive(root, value)
}
private fun searchRecursive(current: Node?, value: Int): Boolean {
if (current == null) {
return false
}
if (value == current.data) {
return true
}
return if (value < current.data) {
searchRecursive(current.left, value)
} else {
searchRecursive(current.right, value)
}
}
// Delete a value from the tree
fun delete(value: Int) {
root = deleteRecursive(root, value)
}
private fun deleteRecursive(current: Node?, value: Int): Node? {
if (current == null) {
return null
}
if (value == current.data) {
if (current.left == null && current.right == null) {
return null
}
if (current.right == null) {
return current.left
}
if (current.left == null) {
return current.right
}
val smallestValue = findSmallestValue(current.right!!)
current.data = smallestValue
current.right = deleteRecursive(current.right, smallestValue)
return current
}
if (value < current.data) {
current.left = deleteRecursive(current.left, value)
return current
}
current.right = deleteRecursive(current.right, value)
return current
}
private fun findSmallestValue(root: Node): Int {
return root.left?.let { findSmallestValue(it) } ?: root.data
}
// Find the minimum value in the tree
fun findMin(): Int? {
return findMinRecursive(root)
}
private fun findMinRecursive(node: Node?): Int? {
return node?.left?.let { findMinRecursive(it) } ?: node?.data
}
// Find the maximum value in the tree
fun findMax(): Int? {
return findMaxRecursive(root)
}
private fun findMaxRecursive(node: Node?): Int? {
return node?.right?.let { findMaxRecursive(it) } ?: node?.data
}
// Tree traversal methods
fun inOrderTraversal(node: Node?) {
if (node != null) {
inOrderTraversal(node.left)
println(node.data)
inOrderTraversal(node.right)
}
}
fun preOrderTraversal(node: Node?) {
if (node != null) {
println(node.data)
preOrderTraversal(node.left)
preOrderTraversal(node.right)
}
}
fun postOrderTraversal(node: Node?) {
if (node != null) {
postOrderTraversal(node.left)
postOrderTraversal(node.right)
println(node.data)
}
}
}
// Client code
fun main() {
val bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
bst.insert(60)
bst.insert(80)
println("In-order traversal:")
bst.inOrderTraversal(bst.root)
println("\nPre-order traversal:")
bst.preOrderTraversal(bst.root)
println("\nPost-order traversal:")
bst.postOrderTraversal(bst.root)
println("\nSearch for 40: ${bst.search(40)}")
println("Search for 100: ${bst.search(100)}")
println("\nMinimum value: ${bst.findMin()}")
println("Maximum value: ${bst.findMax()}")
bst.delete(40)
println("\nAfter deleting 40:")
bst.inOrderTraversal(bst.root)
bst.delete(50)
println("\nAfter deleting 50:")
bst.inOrderTraversal(bst.root)
}
Output:
In-order traversal: 20 30 40 50 60 70 80 Pre-order traversal: 50 30 20 40 70 60 80 Post-order traversal: 20 40 30 60 80 70 50 Search for 40: true Search for 100: false Minimum value: 20 Maximum value: 80 After deleting 40: 20 30 50 60 70 80 After deleting 50: 20 30 60 70 80
Explanation:
1. A Binary Search Tree (BST) is a special form of binary tree where for every node, its left child nodes have values less than the node and its right child nodes have values greater than the node.
2. The Node class represents individual nodes of the BST, containing data, left child, and right child.
3. In the BST class:
- The insert method is used to add new nodes to the BST.
- The search method checks if a value is present in the BST.
- The delete method removes a node from the BST.
- The findMin and findMax methods retrieve the minimum and maximum values from the BST, respectively.
- Tree traversal methods (inOrderTraversal, preOrderTraversal, and postOrderTraversal) allow visiting the nodes in a specific order.
4. The client code demonstrates the usage of the BST, including insertion, traversal, search, and deletion operations.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment