Scribd
Upload
11 views2 pages

BST

The document contains a Java implementation of a Binary Search Tree (BST) with methods for searching, deleting nodes, and performing an inorder traversal. It defines a TreeNode class and includes a main method that demonstrates searching for a node and deleting a non-existent node. The inorder traversal is printed before and after the deletion attempt.

Uploaded by

rithwikborra
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
11 views2 pages

BST

The document contains a Java implementation of a Binary Search Tree (BST) with methods for searching, deleting nodes, and performing an inorder traversal. It defines a TreeNode class and includes a main method that demonstrates searching for a node and deleting a non-existent node. The inorder traversal is printed before and after the deletion attempt.

Uploaded by

rithwikborra
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

class TreeNode {

int val;
TreeNode left, right;

TreeNode(int val) {
this.val = val;
this.left = this.right = null;
}
}

public class BST {

public TreeNode search(TreeNode root, int key) {


if (root == null || root.val == key) {
return root;
}

if (key < root.val) {


return search(root.left, key);
}

return search(root.right, key);


}

public TreeNode deleteNode(TreeNode root, int key) {


if (root == null) {
return root;
}

if (key < root.val) {


root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}

root.val = minValue(root.right);
root.right = deleteNode(root.right, root.val);
}

return root;
}

public int minValue(TreeNode root) {


int minValue = root.val;
while (root.left != null) {
minValue = root.left.val;
root = root.left;
}
return minValue;
}

public void inorder(TreeNode root) {


if (root == null) return;
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}

public static void main(String[] args) {


BST bst = new BST();

TreeNode root = new TreeNode(5);


root.left = new TreeNode(3);
root.right = new TreeNode(8);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(7);
root.right.right = new TreeNode(9);

TreeNode searchResult = bst.search(root, 6);


if (searchResult != null) {
System.out.println("Found node with key 6");
} else {
System.out.println("Node with key 6 not found");
}

System.out.println("Inorder traversal before deletion:");


bst.inorder(root);
System.out.println();

root = bst.deleteNode(root, 6);

System.out.println("Inorder traversal after deletion:");


bst.inorder(root);
System.out.println();
}
}

You might also like