Binary Search Tree
// Stack class will be used for iterative versions of recursive algorithms
// Queue interface and LinkedList class will be used to find the level-order traversal of a binary search tree
import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;
public class Main {
// Main function: The driver function
public static void main(String[] args) {
System.out.println("BST = Binary Search Tree");
System.out.println("----------------------------------------------------");
BinarySearchTree tree = new BinarySearchTree("A");
/* Construct the following binary search tree
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
tree.insert(30);
tree.insert(70);
tree.insert(40);
System.out.println("----------------------------------------------------");
tree.preorder();
tree.inorder();
tree.postorder();
tree.levelorder();
System.out.println();
tree.height();
tree.countNodes();
tree.countLeafNodes();
tree.countNonleafNodes();
tree.minimum();
tree.maximum();
tree.range(35, 75);
System.out.println();
tree.isFullTree();
tree.isCompleteTree();
tree.isPerfectTree();
tree.isBinarySearchTree();
System.out.println("----------------------------------------------------");
/* Get the following binary search tree
40
/ \
20 70
\
80 */
tree.delete(60);
tree.delete(30);
tree.delete(50);
tree.delete(10);
tree.search(70);
tree.search(50);
tree.search(10);
System.out.println("----------------------------------------------------");
tree.preorder();
tree.inorder();
tree.postorder();
tree.levelorder();
System.out.println();
tree.height();
tree.countNodes();
tree.countLeafNodes();
tree.countNonleafNodes();
tree.minimum();
tree.maximum();
tree.range(35, 75);
System.out.println();
tree.isFullTree();
tree.isCompleteTree();
tree.isPerfectTree();
tree.isBinarySearchTree();
System.out.println("----------------------------------------------------");
BinarySearchTree tree2 = new BinarySearchTree("B");
tree.isIdentical(tree2);
tree2.copy(tree);
tree.isIdentical(tree2);
System.out.println("----------------------------------------------------");
tree.successor(10);
tree.successor(20);
tree.successor(40);
tree.successor(70);
tree.successor(80);
tree.successor(100);
System.out.println();
tree.predecessor(10);
tree.predecessor(20);
tree.predecessor(40);
tree.predecessor(70);
tree.predecessor(80);
tree.predecessor(100);
System.out.println();
tree.rank(20);
tree.rank(40);
tree.rank(70);
tree.rank(80);
tree.rank(100);
System.out.println();
tree.kthSmallest(1);
tree.kthSmallest(2);
tree.kthSmallest(3);
tree.kthSmallest(4);
tree.kthSmallest(5);
System.out.println();
tree.kthLargest(1);
tree.kthLargest(2);
tree.kthLargest(3);
tree.kthLargest(4);
tree.kthLargest(5);
System.out.println("----------------------------------------------------");
}
}
// Binary Search Tree (BST) class
class BinarySearchTree {
// BST Node class: This class is made a nested private class to adhere to OOP principles.
private class Node {
int key;
Node left, right;
// Constructor for the Node class
public Node(int item)
{ key = item; left = right = null; }
}
private Node root; // Root node of the BST
private String name; // Name given to the BST
// Constructor for the BinarySearchTree class
BinarySearchTree(String treename) {
root = null; name = treename;
System.out.println("BST " + name + " is constructed and initialized");
}
// Search for a node in the BST
public void search(int key) {
System.out.print("Search " + key + " in BST " + name + ": ");
if (searchRecursive(root, key) != null) System.out.println("success");
else System.out.println("fail");
}
// Recursive function for searching for a node in the BST
private Node searchRecursive(Node curr, int key) {
if (curr == null) return curr;
else if (key < curr.key) return searchRecursive(curr.left, key);
else if (key > curr.key) return searchRecursive(curr.right, key);
else /* if (key == curr.key) */ return curr;
}
// Insert a new node in the BST
public void insert(int key) {
System.out.println("Insert " + key + " into BST " + name);
root = insertRecursive(root, key);
//root = insertIterative(key);
}
// Recursive function for inserting a new node in the BST
private Node insertRecursive(Node curr, int key) {
if (curr == null) { curr = new Node(key); return curr; }
else if (key < curr.key) curr.left = insertRecursive(curr.left, key);
else if (key > curr.key) curr.right = insertRecursive(curr.right, key);
return curr; /* if (key == curr.key) */
}
// Delete a node in the BST
public void delete(int key) {
System.out.println("Delete " + key + " from BST " + name);
root = deleteRecursive(root, key);
//root = deleteIterative(root, key);
}
// Recursive helper function for deleting a node in the BST
private Node deleteRecursive(Node curr, int key) {
if (curr == null) return curr;
else if (key < curr.key) curr.left = deleteRecursive(curr.left, key);
else if (key > curr.key) curr.right = deleteRecursive(curr.right, key);
else if (key == curr.key) {
// node has 1 child or 0 children
if (curr.left == null) return curr.right;
// node has 1 child
else if (curr.right == null) return curr.left;
// node has 2 children
else {
// predecessor
curr.key = maximumRecursive(curr.left).key;
curr.left = deleteRecursive(curr.left, curr.key);
/* Successor can also be used instead of predecessor
curr.key = minimumRecursive(curr.right).key;
curr.right = deleteRecursive(curr.right, curr.key); */
}
}
return curr;
}
// Preorder traversal of the BST
public void preorder() {
System.out.print("Preorder traversal of BST " + name + ": ");
preorderRecursive(root);
//preorderIterative(root);
System.out.println();
}
// Preorder traversal of the BST
private void preorderRecursive(Node curr) {
if (curr != null) {
System.out.print(curr.key + " ");
preorderRecursive(curr.left);
preorderRecursive(curr.right);
}
}
// Inorder traversal of the BST
public void inorder() {
System.out.print("Inorder traversal of BST " + name + ": ");
inorderRecursive(root);
//inorderIterative(root);
System.out.println();
}
// Inorder traversal of the BST
private void inorderRecursive(Node curr) {
if (curr != null) {
inorderRecursive(curr.left);
System.out.print(curr.key + " ");
inorderRecursive(curr.right);
}
}
// Postorder traversal of the BST
public void postorder() {
System.out.print("Postorder traversal of BST " + name + ": ");
postorderRecursive(root);
//postorderIterative(root);
System.out.println();
}
// Postorder traversal of the BST
private void postorderRecursive(Node curr) {
if (curr != null) {
postorderRecursive(curr.left);
postorderRecursive(curr.right);
System.out.print(curr.key + " ");
}
}
// Levelorder traversal of the BST
public void levelorder() {
System.out.print("Levelorder traversal of BST " + name + ": ");
levelorderRecursive();
}
// Recursive levelorder traversal of the BST
private void levelorderRecursive() {
int h = heightRecursive(root);
for (int i = 1; i <= h; i++)
printLevelNodes(root, i);
}
private void printLevelNodes(Node curr, int level)
{
if (curr == null) return;
if (level == 1) System.out.print(curr.key + " ");
else if (level > 1) {
printLevelNodes(curr.left, level - 1);
printLevelNodes(curr.right, level - 1);
}
}
// Height of the BST
public void height() {
System.out.println("Height of BST " + name + ": " + heightRecursive(root));
}
// Recursive function to compute the height of the BST
private int heightRecursive(Node curr) {
if (curr == null) return 0;
return Math.max(heightRecursive(curr.left), heightRecursive(curr.right)) + 1;
}
// Count nodes in the BST
public void countNodes() {
System.out.println("Count nodes in BST " + name + ": " + countNodesRecursive(root));
}
// Count leaf nodes in the BST
public void countLeafNodes() {
System.out.println("Count leaf nodes in BST " + name + ": " + countLeafNodesRecursive(root));
}
// Count nonleaf nodes in the BST
public void countNonleafNodes() {
System.out.println("Count nonleaf nodes in BST " + name + ": " + countNonleafNodesRecursive(root));
}
// Recursive function to count the nodes in the BST
private int countNodesRecursive(Node curr) {
if (curr == null) return 0;
else return ( 1 + countNodesRecursive(curr.left) + countNodesRecursive(curr.right) );
}
// Recursive function to count the leaf nodes in the BST
private int countLeafNodesRecursive(Node curr) {
if (curr == null) return 0;
else if (curr.left == null && curr.right == null) return 1;
else return ( countLeafNodesRecursive(curr.left) + countLeafNodesRecursive(curr.right) );
}
// Recursive function to count the nonleaf nodes in the BST
private int countNonleafNodesRecursive(Node curr) {
if (curr == null) return 0;
else if (curr.left == null && curr.right == null) return 0;
else return ( 1 + countNonleafNodesRecursive(curr.left) + countNonleafNodesRecursive(curr.right) );
}
// Minimum key node in the BST
public void minimum() {
if (root == null) System.out.println("Minimum value doesn't exist as BST " + name + " is an empty tree");
else System.out.println("Minimum value in BST " + name + ": " + minimumRecursive(root).key);
}
// Recursive function to find the minimum key node in the BST
private Node minimumRecursive(Node root) {
if (root.left == null) return root;
return minimumRecursive(root.left);
}
// Maximum key node in the BST
public void maximum() {
if (root == null) System.out.println("Maximum value doesn't exist as BST " + name + " is an empty tree");
else System.out.println("Maximum value in BST " + name + ": " + maximumRecursive(root).key);
}
// Recursive function to find the maximum key node in the BST
private Node maximumRecursive(Node root) {
if (root.right == null) return root;
return maximumRecursive(root.right);
}
// Find if the tree is full or not
public void isFullTree() {
System.out.print("Is BST " + name + " a full tree: ");
System.out.println(isFullTreeRecursive(root));
}
// Recursive function to find if the tree is full or not
private boolean isFullTreeRecursive(Node curr) {
if (curr == null) return true;
else if (curr.left == null && curr.right == null) return true;
else if (curr.left != null && curr.right != null) return (isFullTreeRecursive(curr.left) && isFullTreeRecursive(curr.right));
return false;
}
// Find if the tree is complete or not
public void isCompleteTree() {
System.out.print("Is BST " + name + " a complete tree: ");
int numNodes = countNodesRecursive(root);
System.out.println(isCompleteTreeRecursive(root, 0, numNodes));
}
// Recursive function to find if the tree is complete or not
private boolean isCompleteTreeRecursive(Node curr, int index, int numberNodes) {
if (curr == null) return true;
else if (index >= numberNodes) return false;
return ( isCompleteTreeRecursive(curr.left, 2 * index + 1, numberNodes) && isCompleteTreeRecursive(curr.right, 2 * index + 2, numberNodes) );
}
// Find if the tree is perfect or not
public void isPerfectTree() {
System.out.print("Is BST " + name + " a perfect tree: ");
int depth = depthMinimum(root);
System.out.println(isPerfectTreeRecursive(root, depth, 0));
}
// Find the depth of the minimum node in the BST
private int depthMinimum(Node curr) {
int d = 0;
while (curr != null) { d++; curr = curr.left; }
return d;
}
// Recursive function to find if the tree is perfect or not
private boolean isPerfectTreeRecursive(Node curr, int depth, int level) {
if (curr == null) return true;
else if (curr.left == null && curr.right == null) return (depth == level + 1);
else if (curr.left == null || curr.right == null) return false;
else /* if (curr.left != null || curr.right != null) */ return ( isPerfectTreeRecursive(curr.left, depth, level + 1) && isPerfectTreeRecursive(curr.right, depth, level + 1) );
}
// Check if the tree is a BST
public void isBinarySearchTree() {
System.out.print("Is " + name + " a BST: ");
System.out.println(isBSTRecursive(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
// Recursive function to check if the given tree is a BST and its keys are in the range [min, max]
private boolean isBSTRecursive(Node curr, int min, int max)
{
if (curr == null) return true;
else if (curr.key < min || curr.key > max) return false;
else /* if (curr.key >= min && curr.key <= max) */ return (isBSTRecursive(curr.left, min, curr.key - 1) && isBSTRecursive(curr.right, curr.key + 1, max));
}
// Nodes in the BST present in a given range
public void range(int low, int high) {
System.out.print("Range[" + low + "," + high + "] in BST " + name + ": ");
rangeRecursive(root, low, high);
System.out.println();
}
// Recursive function to find the nodes in the BST present in a given range
private void rangeRecursive(Node curr, int low, int high) {
if (curr == null) return;
if (low < curr.key) rangeRecursive(curr.left, low, high);
if (high > curr.key) rangeRecursive(curr.right, low, high);
if (low <= curr.key && high >= curr.key) System.out.print(curr.key + " ");
}
// Check if the given BST is identical to the current BST
public void isIdentical(BinarySearchTree tree) {
System.out.println("Are BSTs " + name + " and " + tree.name + " identical? " + isIdenticalIterative(root, tree.root));
}
// Recursive function to check if two BSTs are identical or not
private boolean isIdenticalRecursive(Node root1, Node root2) {
if (root1 == null && root2 == null) return true;
else if (root1 != null && root2 != null) return (root1.key == root2.key && isIdenticalRecursive(root1.left, root2.left) && isIdenticalRecursive(root1.right, root2.right));
return false;
}
// Copy a BST to the current BST
public void copy(BinarySearchTree tree) {
System.out.println("Copy BST " + tree.name + " to BST " + name);
root = copyIterative(tree.root);
}
// Recursive function to copy BST to the current BST
private Node copyRecursive(Node curr) {
if (curr == null) return null;
Node newnode = new Node(curr.key);
newnode.left = copyRecursive(curr.left);
newnode.right = copyRecursive(curr.right);
return newnode;
}
// Successor of a key in the BST
public void successor(int key) {
System.out.print("Successor of " + key + " in BST " + name + ": ");
Node succ = successorRecursive(root, key);
//Node succ = successorIterative(root, key);
if (succ != null) System.out.println(succ.key);
else System.out.println("does not exist");
}
// Predecessor of a key in the BST
public void predecessor(int key) {
System.out.print("Predecessor of " + key + " in BST " + name + ": ");
Node pred = predecessorRecursive(root, key);
//Node pred = predecessorIterative(root, key);
if (pred != null) System.out.println(pred.key);
else System.out.println("does not exist");
}
// Helper recursive function to find the successor of a key in the BST
private Node successorRecursive(Node curr, int key) {
if (curr == null) return null;
else if (curr.key <= key) return successorRecursive(curr.right, key);
else {
Node left = successorRecursive(curr.left, key);
return (left != null) ? left : curr;
}
}
// Helper recursive function to find the predecessor of a key in the BST
private Node predecessorRecursive(Node curr, int key) {
if (curr == null) return null;
else if (curr.key >= key) return predecessorRecursive(curr.left, key);
else {
Node right = predecessorRecursive(curr.right, key);
return (right != null) ? right : curr;
}
}
// Rank of a node with key k is r if (r-1) keys in the BST are strictly less than k. If key k does not exist, then its rank is 0.
// Get the position of the node in the BST
public void rank(int key) {
System.out.print("Rank of " + key + " in BST " + name + ": ");
Node node = searchRecursive(root, key);
if (node == null) System.out.println("0");
else System.out.println(rankRecursive(root, key));
}
// Recursive function to get the position of the node in the BST
private int rankRecursive(Node curr, int key) {
if (curr == null) return 0;
else if (key < curr.key) return rankRecursive(curr.left, key);
else if (key > curr.key) return ( 1 + countNodesRecursive(curr.left) + rankRecursive(curr.right, key) );
else /* if (key == curr.key) */ return ( 1 + countNodesRecursive(curr.left) );
}
// Find the kth smallest element in BST
public void kthSmallest(int k) {
Node node = kthSmallestRecursive(root, k);
System.out.print("kth smallest element (k = " + k + ") in BST " + name + ": ");
if (node == null) System.out.println("does not exist");
else System.out.println(node.key);
}
// Recursive function to return the kth smallest element in the BST
private Node kthSmallestRecursive(Node curr, int k) {
if (curr == null) return null;
int count = countNodesRecursive(curr.left) + 1;
if (count == k) return curr;
else if (count > k) return kthSmallestRecursive(curr.left, k);
else /* if (count < k) */ return kthSmallestRecursive(curr.right, k - count);
}
// Find the kth largest element in BST
public void kthLargest(int k) {
Node node = kthLargestRecursive(root, k);
System.out.print("kth largest element (k = " + k + ") in BST " + name + ": ");
if (node == null) System.out.println("does not exist");
else System.out.println(node.key);
}
// Recursive function to return the kth largest element in the BST
private Node kthLargestRecursive(Node curr, int k) {
if (curr == null) return null;
int count = countNodesRecursive(curr.right) + 1;
if (count == k) return curr;
else if (count > k) return kthLargestRecursive(curr.right, k);
else /* if (count < k) */ return kthLargestRecursive(curr.left, k - count);
}
//-------------------------------------------------------------------
// ITERATIVE FUNCTIONS ----------------------------------------------
//-------------------------------------------------------------------
// Iterative levelorder traversal of the BST
private void levelorderIterative() {
Queue queue = new LinkedList<>();
queue.add(root);
Node first;
while (!queue.isEmpty()) {
first = queue.poll();
System.out.print(first.key + " ");
if (first.left != null) queue.add(first.left);
if (first.right != null) queue.add(first.right);
}
System.out.println();
}
// Iterative function for searching for a node in the BST
private Node searchIterative(Node curr, int key) {
while (curr != null) {
if (key < curr.key) curr = curr.left;
else if (key > curr.key) curr = curr.right;
else /* if (key == curr.key) */ return curr;
}
return null;
}
// Iterative function for inserting a new node in the BST
private Node insertIterative(int key) {
Node curr = root; Node parent = null;
if (root == null) return new Node(key);
// find the parent node
while (curr != null) {
parent = curr;
if (key < curr.key) curr = curr.left;
else if (key > curr.key) curr = curr.right;
else return root;
}
// assign the new node to the parent
if (key < parent.key) parent.left = new Node(key);
else /* if (key > parent.key) */ parent.right = new Node(key);
return root;
}
// Iterative helper function for deleting a node in the BST
private Node deleteIterative(Node root, int key) {
Node curr = root; Node parent = null;
// find the parent node
while (curr != null && curr.key != key) {
parent = curr;
if (key < curr.key) curr = curr.left;
else if (key > curr.key) curr = curr.right;
}
if (parent == null) return deleteIterative(curr);
else if (parent.left == curr) parent.left = deleteIterative(curr);
else if (parent.right == curr) parent.right = deleteIterative(curr);
return root;
}
private Node deleteIterative(Node curr) {
if (curr != null) {
if (curr.left == null && curr.right == null)
return null;
else if (curr.left != null && curr.right != null) {
Node predecessor = deletePredecessor(curr);
curr.key = predecessor.key;
/* Successor can also be used instead of predecessor
Node successor = deleteSuccessor(curr);
curr.key = successor.key; */
}
else if (curr.left != null) curr = curr.left;
else curr = curr.right;
}
return curr;
}
private Node deletePredecessor(Node curr) {
Node parent = curr; curr = curr.left;
boolean isLeftChild = (curr.right == null);
while (curr.right != null) { parent = curr; curr = curr.right; }
if (isLeftChild) parent.left = curr.left;
else parent.right = curr.left;
curr.left = null;
return curr;
}
private Node deleteSuccessor(Node curr) {
Node parent = curr; curr = curr.right;
boolean isRightChild = (curr.left == null);
while (curr.left != null) { parent = curr; curr = curr.left; }
if (isRightChild) parent.right = curr.right;
else parent.left = curr.right;
curr.right = null;
return curr;
}
// Helper iterative function to find the predecessor of a key in the BST
private Node predecessorIterative(Node curr, int key) {
Node predecessor = null;
while (curr != null) {
if (key <= curr.key) curr = curr.left;
else { predecessor = curr; curr = curr.right; }
}
return predecessor;
}
// Helper iterative function to find the successor of a key in the BST
private Node successorIterative(Node curr, int key) {
Node successor = null;
while (curr != null) {
if (key >= curr.key) curr = curr.right;
else { successor = curr; curr = curr.left; }
}
return successor;
}
// Iterative preorder traversal of the BST
private void preorderIterative(Node root) {
if (root == null) return;
Stack stack = new Stack();
stack.push(root);
while (!stack.empty()) {
Node curr = stack.pop();
System.out.print(curr.key + " ");
if (curr.right != null) stack.push(curr.right);
if (curr.left != null) stack.push(curr.left);
}
}
// Iterative inorder traversal of the BST
private void inorderIterative(Node root) {
Stack stack = new Stack();
Node curr = root;
while (!stack.empty() || curr != null) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
}
else {
curr = stack.pop();
System.out.print(curr.key + " ");
curr = curr.right;
}
}
}
// Iterative postorder traversal of the BST
private void postorderIterative(Node root) {
Stack stack = new Stack();
stack.push(root);
// Create stack to store postorder traversal
Stack postorderTraversal = new Stack();
while (!stack.empty()) {
Node curr = stack.pop();
postorderTraversal.push(curr.key);
if (curr.left != null) stack.push(curr.left);
if (curr.right != null) stack.push(curr.right);
}
// print postorder traversal
while (!postorderTraversal.empty()) {
System.out.print(postorderTraversal.pop() + " ");
}
}
//Iterative function to compute the height of the BST
public int heightIterative(Node curr) {
if (curr == null) return 0;
Queue queue = new LinkedList<>();
queue.add(curr);
Node front = null; int height = 0;
while (!queue.isEmpty()) {
int size = queue.size(); // total number of nodes at the current level
while (size > 0) {
size--;
front = queue.poll();
if (front.left != null) queue.add(front.left);
if (front.right != null) queue.add(front.right);
}
height++;
}
return height;
}
// Iterative function to count the nodes in the BST
private int countNodesIterative(Node curr) {
if (curr == null) return 0;
int count = 0;
Queue queue = new LinkedList<>();
queue.add(curr);
Node front = null;
while (!queue.isEmpty()) {
front = queue.poll();
if (front.left != null) queue.add(front.left);
if (front.right != null) queue.add(front.right);
count++;
}
return count;
}
// Iterative function to count the leaf nodes in the BST
private int countLeafNodesIterative(Node curr) {
if (curr == null) return 0;
int count = 0;
Queue queue = new LinkedList<>();
queue.add(curr);
Node front = null;
while (!queue.isEmpty()) {
front = queue.poll();
if (front.left != null) queue.add(front.left);
if (front.right != null) queue.add(front.right);
if (front.left == null && front.right == null) count++;
}
return count;
}
// Iterative function to count the nonleaf nodes in the BST
private int countNonleafNodesIterative(Node curr) {
if (curr == null) return 0;
int count = 0;
Queue queue = new LinkedList<>();
queue.add(curr);
Node front = null;
while (!queue.isEmpty()) {
front = queue.poll();
if (front.left != null) queue.add(front.left);
if (front.right != null) queue.add(front.right);
if (front.left != null || front.right != null) count++;
}
return count;
}
// Iterative function to find the minimum key node in the BST
private Node minimumIterative(Node curr) {
while (curr.left != null) curr = curr.left;
return curr;
}
// Iterative function to find the maximum key node in the BST
private Node maximumIterative(Node curr) {
while (curr.right != null) curr = curr.right;
return curr;
}
// Iterative function to find if the tree is full or not
private boolean isFullTreeIterative(Node curr) {
if (curr == null) return true;
Queue queue = new LinkedList<>();
queue.add(curr);
Node front = null;
while (!queue.isEmpty()) {
front = queue.poll();
if (front.left == null && front.right == null)
continue;
if (front.left == null || front.right == null)
return false;
queue.add(front.left);
queue.add(front.right);
}
return true;
}
// Iterative function to find if the tree is complete or not
private boolean isCompleteTreeIterative(Node curr) {
if(curr == null) return true;
Queue queue =new LinkedList<>();
boolean flag = false;
queue.add(curr);
Node front = null;
while(!queue.isEmpty()) {
front = queue.poll();
if (front.left != null) {
if (flag == true) return false;
queue.add(front.left);
}
else
flag = true;
if (front.right != null) {
if(flag == true) return false;
queue.add(front.right);
}
else
flag = true;
}
return true;
}
// Iterative function to find if the tree is perfect or not
private boolean isPerfectTreeIterative(Node curr) {
Queue queue = new LinkedList<>();
queue.add(curr);
Node front = null;
boolean flag = false;
while (!queue.isEmpty()) {
front = queue.poll();
if (front.left != null && front.right != null) {
if (flag == true) return false;
else {
queue.add(front.left);
queue.add(front.right);
}
}
else if (front.left == null && front.right == null) flag = true;
else if (front.left == null || front.right == null) return false;
}
return true;
}
// Iterative function to find all nodes in the BST from a given range
private void rangeIterative(Node curr, int low, int high) {
if (curr == null) return;
while (curr != null) {
if (curr.left == null) {
if (curr.key <= high && curr.key >= low)
System.out.print(curr.key + " ");
curr = curr.right;
}
else {
Node predecessor = curr.left;
while (predecessor.right != null && predecessor.right != curr) predecessor = predecessor.right;
if (predecessor.right == null) {
predecessor.right = curr;
curr = curr.left;
}
else {
predecessor.right = null;
if (curr.key <= high && curr.key >= low)
System.out.print(curr.key + " ");
curr = curr.right;
}
}
}
}
// Iterative algorithm to check if trees are identical
private boolean isIdenticalIterative(Node root1, Node root2) {
if (root1 == null && root2 == null) return true;
if (root1 == null || root2 == null) return false;
Queue queue1 = new LinkedList<>();
Queue queue2 = new LinkedList<>();
queue1.add(root1);
queue2.add(root2);
while (!queue1.isEmpty() && !queue2.isEmpty()) {
Node front1 = queue1.poll();
Node front2 = queue2.poll();
if (front1.key != front2.key) return false;
if (front1.left != null && front2.left != null) {
queue1.add(front1.left);
queue2.add(front2.left);
}
else if (front1.left != null || front2.left != null)
return false;
if (front1.right != null && front2.right != null) {
queue1.add(front1.right);
queue2.add(front2.right);
}
else if (front1.right != null || front2.right != null)
return false;
}
return true;
}
// Iterative function to copy BST to the current BST
private Node copyIterative(Node root1) {
if (root1 == null) return null;
Queue queue1 = new LinkedList<>();
queue1.add(root1);
Node front1;
Queue queue2 = new LinkedList<>();
Node root2 = new Node(root1.key);
queue2.add(root2);
Node front2;
while (!queue1.isEmpty()) {
front1 = queue1.poll();
front2 = queue2.poll();
if (front1.left != null) {
queue1.add(front1.left);
front2.left = new Node(front1.left.key);
queue2.add(front2.left);
}
if (front1.right != null) {
queue1.add(front1.right);
front2.right= new Node(front1.right.key);
queue2.add(front2.right);
}
}
return root2;
}
// Iterative function to get the position of the node in the BST
private int rankIterative(Node root, int key) {
int rank = 0;
Stack stack = new Stack();
Node curr = root;
while (!stack.empty() || curr != null) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
}
else {
curr = stack.pop();
rank++;
if (curr.key == key) return rank;
curr = curr.right;
}
}
return 0;
}
// Iterative function to find the kth smallest element in the BST
private Node kthSmallestIterative(Node curr, int k) {
int count = 0;
Node kthsmallest = null;
while (curr != null) {
if (curr.left == null) {
count++;
if (count == k) kthsmallest = curr;
curr = curr.right;
}
else {
Node predecessor = curr.left;
while (predecessor.right != null && predecessor.right != curr)
predecessor = predecessor.right;
if (predecessor.right == null) {
predecessor.right = curr;
curr = curr.left;
}
else {
predecessor.right = null;
count++;
if (count == k) kthsmallest = curr;
curr = curr.right;
}
}
}
return kthsmallest;
}
// Iterative function to find the kth largest element in the BST
private Node kthLargestIterative(Node curr, int k) {
int count = 0;
Node kthlargest = null;
while (curr != null) {
if (curr.right == null) {
count++;
if (count == k) kthlargest = curr;
curr = curr.left;
}
else {
Node successor = curr.right;
while (successor.left != null && successor.left != curr)
successor = successor.left;
if (successor.left == null) {
successor.left = curr;
curr = curr.right;
}
else {
successor.left = null;
count++;
if (count == k) kthlargest = curr;
curr = curr.left;
}
}
}
return kthlargest;
}
}