Binary Search Tree
A Binary Search Tree (BST) is a binary tree in which left subtree of a node contains a key less than the node's key and right subtree of a node contains only the nodes with key greater than the node's key. Left and right subtree must each also be a binary search tree.
import java.util.Stack;
class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
Node buildBST(Node root, int key) {
if (root == null)
return new Node(key);
if (root.data > key)
root.left = buildBST(root.left, key);
else if (root.data < key)
root.right = buildBST(root.right, key);
return root;
}
boolean search(Node root, int key) {
if (root == null)
return false;
if (root.data == key)
return true;
else if (root.data > key)
return search(root.left, key);
return search(root.right, key);
}
Node inorderSucc(Node root) {
Node curr = root;
while (curr.left != null)
curr = curr.left;
return curr;
}
Node delete(Node root, int key) {
if (root == null)
return null;
if (root.data > key)
root.left = delete(root.left, key);
else if (root.data < key)
root.right = delete(root.right, key);
else {
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
else {
Node temp = inorderSucc(root.right);
root.data = temp.data;
root.right = delete(root.right, temp.data);
}
}
return root;
}
int preIdx = 0;
Node buildTreeWithPre(int preorder[], int key, int min, int max, int n) {
if (preIdx >= n)
return null;
Node root = null;
if (key > min && key < max) {
root = new Node(key);
preIdx++;
if (preIdx < n)
root.left = buildTreeWithPre(preorder, preorder[preIdx], min, key, n);
if (preIdx < n)
root.right = buildTreeWithPre(preorder, preorder[preIdx], key, max, n);
}
return root;
}
boolean isBST(Node root, Node max, Node min) {
if (root == null)
return true;
if (max != null && max.data <= root.data)
return false;
if (min != null && min.data >= root.data)
return false;
boolean leftValid = isBST(root.left, root, min);
boolean rightValid = isBST(root.right, max, root);
return leftValid && rightValid;
}
Node sortedArrayToBST(int arr[], int start, int end) {
if (start > end)
return null;
int mid = start + (end - start) / 2;
Node root = new Node(arr[mid]);
root.left = sortedArrayToBST(arr, start, mid - 1);
root.right = sortedArrayToBST(arr, mid + 1, end);
return root;
}
void zigZagTraversal(Node root) {
if (root == null)
return;
Stack<Node> currLevel = new Stack<Node>();
Stack<Node> nextLevel = new Stack<Node>();
boolean leftToRight = true;
currLevel.push(root);
while (!currLevel.isEmpty()) {
Node temp = currLevel.pop();
if (temp != null) {
System.out.println(temp.data + " ");
if (leftToRight) {
if (temp.left != null)
nextLevel.push(temp.left);
if (temp.right != null)
nextLevel.push(temp.right);
} else {
if (temp.right != null)
nextLevel.push(temp.right);
if (temp.left != null)
nextLevel.push(temp.left);
}
}
if (currLevel.isEmpty()) {
leftToRight = !leftToRight;
while (!nextLevel.isEmpty())
currLevel.push(nextLevel.pop());
}
}
}
boolean areIdenticals(Node root1, Node root2) {
if (root1 == null && root2 == null)
return true;
else if (root1 == null || root2 == null)
return false;
else {
boolean cond1 = root1.data == root2.data;
boolean cond2 = areIdenticals(root1.left, root2.left);
boolean cond3 = areIdenticals(root1.right, root2.right);
if (cond1 && cond2 && cond3)
return true;
return false;
}
}
}
Comments
Post a Comment