import java.util.

Scanner; boolean left =

scanner.nextBoolean();
class BinaryTree {
if (left) {
public BinaryTree() {
System.out.println("Enter the
}
value of the left of " + node.value);
private static class Node {
int value = scanner.nextInt();
int value;
node.left = new Node(value);
Node left;
populate(scanner, node.left);
Node right;
}
public Node(int value) {
System.out.println("Do you want
this.value = value; to enter right of " + node.value);
} boolean right =
} scanner.nextBoolean();

private Node root; if (right) {

// insert elements System.out.println("Enter the

value of the right of " + node.value);
public void populate(Scanner
scanner) { int value = scanner.nextInt();

System.out.println("Enter the root node.right = new Node(value);

Node: "); populate(scanner, node.right);
int value = scanner.nextInt(); }
root = new Node(value); }
populate(scanner, root); public void display() {
} display(this.root, "");
private void populate(Scanner }
scanner, Node node) {
private void display(Node node,
System.out.println("Do you want String indent) {
to enter left of " + node.value);
if (node == null) {
 return; public void preOrder() {
} preOrder(root);
System.out.println(indent + }
node.value);
private void preOrder(Node node) {
display(node.left, indent + "\t");
if (node == null) {
display(node.right, indent + "\t");
return;
}
}
public void prettyDisplay() {
System.out.print(node.value + "
prettyDisplay(root, 0); ");
} preOrder(node.left);
private void prettyDisplay(Node preOrder(node.right);
node, int level) {
}
if (node == null) {
public void inOrder() {
return;
preOrder(root);
}
}
prettyDisplay(node.right, level +
private void inOrder(Node node) {
1);
if (node == null) {
if (level != 0) {
return;
for (int i = 0; i < level - 1; i++) {
}
System.out.print("|\t\t");
preOrder(node.left);
}
System.out.print(node.value + "
System.out.println("|------->" +
");
node.value);} else {
preOrder(node.right);
System.out.println(node.value);}
}
prettyDisplay(node.left, level + 1);
public void postOrder() {
}
preOrder(root);
 } private Node root;
private void postOrder(Node node) public BST() {
{
}
if (node == null) {
public int height(Node node) {
return;
if (node == null) {
}
return -1;}
preOrder(node.left);
return node.height; }
preOrder(node.right);
public boolean isEmpty() {
System.out.print(node.value + "
return root == null;
");
}
}
public void insert(int value) {
}
root = insert(value, root);
BST
}
class BST {
private Node insert(int value, Node
public class Node { node) { if (node == null) {
private int value; node = new Node(value);
private Node left; return node; }
private Node right; if (value < node.value) {
private int height; node.left = insert(value,
public Node(int value) { node.left); }

this.value = value; if (value > node.value) {

} node.right = insert(value,
node.right);
public int getValue() {
}
return value;
}
}
 node.height = return Math.abs(height(node.left)
Math.max(height(node.left), - height(node.right)) <= 1 &&
height(node.right)) + 1; balanced(node.left) &&
balanced(node.right); }
return node; }
public void display() {
public void populate(int[] nums) {
display(this.root, "Root Node: ");
for (int i = 0; i < nums.length; i++)
{ }
this.insert(nums[i]); } } private void display(Node node,
String details) {
public void populatedSorted(int[]
nums) { if (node == null) {
populatedSorted(nums, 0, return;
nums.length); }
}
private void populatedSorted(int[]
System.out.println(details +
nums, int start, int end) {
node.value);
if (start >= end) {
display(node.left, "Left child of " +
return; } node.value + " : ");
int mid = (start + end) / 2; display(node.right, "Right child of
" + node.value + " : ");
this.insert(nums[mid]);
}
populatedSorted(nums, start,
mid); MAIN FILE –
populatedSorted(nums, mid + 1, import java.util.Scanner;
end); }
public class Main {
public boolean balanced() {
public static void main(String[]
return balanced(root); } args) {
private boolean balanced(Node // Scanner scanner = new
node) { Scanner(System.in);
if (node == null) { // BinaryTree tree = new
return true; } BinaryTree();
 // tree.populate(scanner); public int height() {
// tree.prettyDisplay(); return height(root);
}
BST tree = new BST(); private int height(Node node) {
int[] nums = { 5, 2, 7, 1, 4, 6, 9, 8, if (node == null) {
3, 10 };
return -1;
tree.populate(nums);
}
tree.display();
return node.height;
AVL –
}
class AVL {
public void insert(int value) {
public class Node {
root = insert(value, root);
private int value;
}
private Node left;
private Node insert(int value, Node
private Node right; node) {
private int height; if (node == null) {
public Node(int value) { node = new Node(value);
this.value = value; return node;
} }
public int getValue() { if (value < node.value) {
return value; node.left = insert(value,
node.left);
}
}
}
if (value > node.value) {
private Node root;
node.right = insert(value,
public AVL() {
node.right);
}
}
 node.height = if(height(node.right.left) -
Math.max(height(node.left), height(node.right.right) < 0) {
height(node.right)) + 1;
// right right case
return rotate(node);
return leftRotate(node);
}
}
if(height(node.right.left) -
private Node rotate(Node node) { height(node.right.right) > 0) {
if (height(node.left) - // left right case
height(node.right) > 1) {
node.right =
// left heavy rightRotate(node.right);
if(height(node.left.left) - return leftRotate(node);
height(node.left.right) > 0) {
}
// left left case
return node;
return rightRotate(node);
}
}
public Node rightRotate(Node p) {
if(height(node.left.left) -
Node c = p.left;
height(node.left.right) < 0) {
Node t = c.right;
// left right case
c.right = p;
node.left =
leftRotate(node.left); p.left = t;

return rightRotate(node); p.height =

Math.max(height(p.left),
}
height(p.right) + 1);
}
c.height =
if (height(node.left) - Math.max(height(c.left),
height(node.right) < -1) { height(c.right) + 1);
// right heavy return c;
}
 public Node leftRotate(Node c) { if (start >= end) {
Node p = c.right; return;
Node t = p.left; }
p.left = c; int mid = (start + end) / 2;
c.right = t; this.insert(nums[mid]);
p.height = populatedSorted(nums, start,
Math.max(height(p.left), mid);
height(p.right) + 1);
populatedSorted(nums, mid + 1,
c.height = end);
Math.max(height(c.left),
}
height(c.right) + 1);
public void display() {
return p;
display(this.root, "Root Node: ");
}
}
public void populate(int[] nums) {
private void display(Node node,
for (int i = 0; i < nums.length; i++)
String details) {
{
if (node == null) {
this.insert(nums[i]);
return;
}
}
}
System.out.println(details +
node.value);
public void populatedSorted(int[]
display(node.left, "Left child of " +
nums) {
node.value + " : ");
populatedSorted(nums, 0,
display(node.right, "Right child of
nums.length);
" + node.value + " : ");
}
}
private void populatedSorted(int[]
public boolean isEmpty() {
nums, int start, int end) {
return root == null;
 } this.endInterval = endInterval;
public boolean balanced() { }
return balanced(root); }
} Node root;
private boolean balanced(Node public SegmentTree(int[] arr) {
node) {
// create a tree using this array
if (node == null) {
this.root = constructTree(arr, 0,
return true; arr.length - 1);
} }
return Math.abs(height(node.left) private Node constructTree(int[]
- height(node.right)) <= 1 && arr, int start, int end) {
balanced(node.left) &&
if(start == end) {
balanced(node.right);
// leaf node
}
Node leaf = new Node(start,
}
end);
SEGMENT TREES : leaf.data = arr[start];
class SegmentTree { return leaf;
private static class Node { }
int data; // create new node with index
int startInterval; you are at

int endInterval; Node node = new Node(start,

end);
Node left;
int mid = (start + end) / 2;
Node right;
node.left = this.constructTree(arr,
public Node (int startInterval, int
start, mid);
endInterval) {
node.right =
this.startInterval = startInterval;
this.constructTree(arr, mid + 1, end);
 node.data = node.left.data + System.out.println(str + '\n');
node.right.data;
// call recursion
return node;
if(node.left != null) {
}
display(node.left); }
public void display() {
if(node.right != null) {
display(this.root);
display(node.right) }}
}
// query
private void display(Node node) {
public int query(int qsi, int qei) {
String str = "";
return this.query(this.root, qsi,
if(node.left != null) { qei); }
str = str + "Interval=[" + private int query(Node node, int
node.left.startInterval + "-" + qsi, int qei) {
node.left.endInterval + "] and data:
if(node.startInterval >= qsi &&
" + node.left.data + " => ";
node.endInterval <= qei) {
} else {
// node is completely lying inside
str = str + "No left child"; } query
// for current node return node.data;
str = str + "Interval=[" + } else if (node.startInterval > qei
node.startInterval + "-" + || node.endInterval < qsi) {
node.endInterval + "] and data: " +
// completely outside
node.data + " <= ";
return 0;
if(node.right != null) {
} else {
str = str + "Interval=[" +
node.right.startInterval + "-" + return this.query(node.left, qsi,
node.right.endInterval + "] and data: qei) + this.query(node.right, qsi,
" + node.right.data; qei); } }

} else { // update

str = str + "No right child"; }

 public void update(int index, int
value) {
this.root.data = update(this.root,
index, value); }
private int update(Node node, int
index, int value) {
if (index >= node.startInterval&&
index <= node.endInterval){
if(index == node.startInterval &&
index == node.endInterval) {
node.data = value;
return node.data;
} else {
int leftAns = update(node.left,
index, value);
int rightAns =
update(node.right, index, value);
node.data = leftAns + rightAns;
return node.data;
}
}
return node.data;
}
}