Practice recursion isHeap isComplete isBST
import java.io.*;
import java.util.*;
// Recursion practice
class Solution {
class Node {
int value;
Node left;
Node right;
public Node(int value){
this.value = value;
}
public void inOrderPrint() {
if(this.left != null) {
this.left.inOrderPrint();
}
System.out.print(this.value + ", ");
if(this.right != null) {
this.right.inOrderPrint();
}
}
}
public Node insertBS(Node root, int value) {
if(root == null) {
return new Node(value);
}
if(value > root.value) {
root.right = insertBS(root.right, value);
} else {
root.left = insertBS(root.left, value);
}
return root;
}
public Node insertLO(int[] arr, int i) {
Node root = null;
if(i>=0 && i < arr.length) {
root = new Node(arr[i]);
root.left = insertLO(arr, 2*i+1);
root.right = insertLO(arr, 2*i+2);
}
return root;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] input = {
{4,2,6,1,3,5,7},
{1,2,3,4,5,6,7},
{7,5,6,4,3,2,1},
{97,46,37,12,3,7,31,6,9},
{97,46,37,12,3,7,31,11,10,2,4},
};
for(int i=0; i< input.length; i++) {
System.out.println("Input: " + Arrays.toString(input[i]));
System.out.print("InOrder: ");
Node tree = solution.insertLO(input[i], 0);
tree.inOrderPrint();
System.out.println("\nisBST:" + solution.isBST(tree) + "\nisComplete: " + solution.isComplete(tree) + "\nisHeap:" + solution.isHeap(tree));
System.out.println();
}
int insertInput[] = {4,2,6,1,3,5,7};
Node tree = solution.insertLO(insertInput, 0);
System.out.print("BST: ");
tree.inOrderPrint();
solution.insertBS(tree,8);
System.out.print("\nAfter Insert: ");
tree.inOrderPrint();
System.out.println();
}
public int countNodes(Node root) {
if(root == null) return 0;
return 1+ countNodes(root.left) + countNodes(root.right);
}
public boolean isComplete(Node root) {
int nodes = countNodes(root);
return isComplete(root,0,nodes);
}
private boolean isComplete(Node root,int i, int nodes) {
if(root == null) return true;
if(i >= nodes) return false;
return isComplete(root.left, 2*i+1, nodes) && isComplete(root.right, 2*i+2, nodes);
}
public boolean isHeap(Node root) {
if(root == null) return true;
return isComplete(root) && isHeapHelper(root);
}
public boolean isHeapHelper(Node root) {
if(root.left == null && root.right == null) return true;
if(root.right == null) {
return root.value >= root.left.value;
} else{
if(root.value >= root.left.value && root.value >= root.right.value) {
return isHeapHelper(root.left) && isHeapHelper(root.right);
} else {
return false;
}
}
}
public boolean isBST(Node root){
return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isBST(Node root, int min, int max) {
if(root == null) return true;
if(root.value < min || root.value > max) return false;
return isBST(root.left, min, root.value-1) &&
isBST( root.right, root.value+1, max );
}
}