public Node getBST(){
BST bst = new BST();
Node root= new Node(45);
bst.insert(root, 20);
bst.insert(root, 60);
bst.insert(root, 21);
bst.insert(root, 19);
bst.insert(root, 55);
bst.insert(root, 65);
return root;
}
public Node getMirroredBST(){
Node root= new Node(45);
root.lc=new Node(60);
root.rc=new Node(20);
root.lc.lc= new Node(65);
root.lc.rc = new Node(55);
root.rc.lc= new Node(21);
root.rc.rc= new Node (19);
return root;
}
public Node getBSTSample(){
Node root= new Node(4);
root.lc=new Node(2);
root.rc=new Node(6);
root.lc.lc=new Node(1);
root.lc.rc=new Node(3);
root.rc.lc= new Node(5);
root.rc.rc=new Node(6);
return root;
}
/**
* predefined we send min to integer min and max to integer max
*
* when go to left then max will be root (update)
* when go to right then min will be root
*
*/
public boolean isBST(Node root, int min, int max){
if(root==null){return true;}
if(root.data>min && root.data<max){
return isBST(root.lc,min,root.data) && isBST(root.rc,root.data,max);
}
return false;
}
public boolean isMirrorTree(Node first,Node second){
boolean isMirrored=false;
//if both tree's root are null they are mirrored
if(first==null && second==null) return true;
//if node of one tree is null and corresponding other tree's node is not null
// they are not mirrored
else if((first==null && second!=null) || first!=null && second==null){
return false;
}
else {
// if both corresponding mirrored node are same
if(first.data==second.data) {
isMirrored=true;
}
else {
return false;
}
// take one tree's left node and second's tree right node
return isMirrored && isMirrorTree(first.lc, second.rc) && isMirrorTree(first.rc,second.lc);
}
}
public boolean isBSTSame(Node first, Node second){
boolean isSame=false;
if(first==null && second==null) return true;
else if((first==null && second!=null)||(first!=null && second==null)){
return false;
}
else{
if(first.data==second.data){
isSame=true;
}
else return false;
return isSame && isBSTSame(first.lc,second.lc) && isBSTSame(first.rc,second.rc);
}
}
public void levelOrderTraversal(Node root){
if(root!=null){
if(nodeQueue.isEmpty()){
nodeQueue.add(root);
}
if(root.lc!=null){
nodeQueue.add(root.lc);
}
if(root.rc!=null){
nodeQueue.add(root.rc);
}
levelOrderTraversal(root.lc);
levelOrderTraversal(root.rc);
}
}
public void zigZagTraversal(Node root,int level){
if(root!=null){
if(nodeQueue.isEmpty()){
nodeQueue.add(root);
}
if(level%2==0){
if(root.lc!=null){
nodeQueue.add(root.lc);
}
if (root.rc != null) {
nodeQueue.add(root.rc);
}
zigZagTraversal(root.lc,level+1);
zigZagTraversal(root.rc,level+1);
}
else{
if(root.rc!=null){
nodeQueue.add(root.rc);
}
if (root.lc != null) {
nodeQueue.add(root.lc);
}
zigZagTraversal(root.lc,level+1);
zigZagTraversal(root.rc,level+1);
}
}
}
public boolean isSibling(Node root, int left,int right){
if(root==null || root.lc==null || root.rc==null){
return false;
}
else{
return (left==root.lc.data && right==root.rc.data)|| (left==root.rc.data && right==root.lc.data)||
isSibling(root.lc,left, right) || isSibling(root.rc, left, right);
}
}
public Node getCommonAncestorBST(Node root,int a, int b){
if(root==null) return null;
else{
if(a==root.data||b==root.data) return root;
else if(a<root.data && b<root.data){
return getCommonAncestorBST(root.lc, a, b);
}
else if(a>root.data && b>root.data){
return getCommonAncestorBST(root.rc, a, b);
}
else if((a<root.data && b>root.data)|| (a>root.data && b<root.data)){
return root;
}
}
return null;
}
public Node getCommonAncestor(Node root, int a, int b){
if (root == null) {
return null;
}
if(root.data==a||root.data==b){
return root;
}
Node left=getCommonAncestor(root.lc,a, b);
Node right=getCommonAncestor(root.rc,a,b);
if(left!=null && right!=null) return root;
if(left==null) return right; else return left;
}
//finds distance from root to given data node. result distance is one less pathLength method returns
public int pathLength(Node root, int data){
if(root!=null){
int pathLength=0;
//
if(root.data==data||(pathLength=pathLength(root.lc,data))>0||(pathLength=pathLength(root.rc,data))>0){
return pathLength+1;
}
return 0;
}
return 0;
}
public int distanceBetweenTwoNode(Node root, int data1,int data2){
if(root!=null){
int data1DistanceFromRoot= pathLength(root,data1)-1;
int data2DistanceFromRoot = pathLength(root, data2)-1;
Node csaNode = getCommonAncestor(root, data1, data2);
if(null==csaNode)return -1;
int csaDistanceFromRoot= pathLength(root,csaNode.data)-1;
int distance=data1DistanceFromRoot+data2DistanceFromRoot- 2* csaDistanceFromRoot;
return distance;
}
return 0;
}
public void levelOrderTraversal(Node root,int level){
if(root!=null && level>-1){
if(level==0){
System.out.print(root.data+" ");
}
else{
levelOrderTraversal(root.lc, level-1);
levelOrderTraversal(root.rc,level-1);
}
}
}
public void allLevelOrderTraversal(Node root){
for(int i=0; i<getMaxDepth(root);i++){
levelOrderTraversal(root, i);
System.out.println(" --> Level:"+i);
}
}
public int getMaxDepth(Node root){
if(root==null){
return 0;
}
else{
int leftDepth=getMaxDepth(root.lc);
int rightDepth=getMaxDepth(root.rc);
if(leftDepth>rightDepth){
return leftDepth+1;
}
else{
return rightDepth+1;
}
}
}
public Node convertToDLLUtil(Node root){
if(root==null) return root;
if(root.lc!=null){
Node left = convertToDLLUtil(root.lc);
while(left.rc!=null) left=left.rc;
left.rc=root;
root.lc=left;
}
if(root.rc!=null){
Node right = convertToDLLUtil(root.rc);
while(right.lc!=null) right=right.lc;
root.rc=right;
right.lc=root;
}
return root;
}
public Node convertToDll(Node root){
Node node = convertToDLLUtil(root);
while (node.lc!=null){
node=node.lc;
}
return node;
}
public void boundaryView(Node root){
printLeftBoundary(root);
printLeaves(root);
printRightBoundary(root);
}
public void printLeftBoundary(Node root){
if(root!=null){
if(root.lc!=null){
System.out.println(root.data);
printLeftBoundary(root.lc);
}
else if(root.rc!=null){
System.out.println(root.data);
printLeftBoundary(root.rc);
}
}
}
public void printRightBoundary(Node root){
if(root!=null){
if(root.rc!=null){
printRightBoundary(root.rc);
System.out.println(root.data);
}
else if(root.rc!=null){
printRightBoundary(root.lc);
System.out.println(root.data);
}
}
}
public void printLeaves(Node root){
if(root!=null){
if(root.lc==null || root.rc==null){
System.out.println(root.data);
}
printLeaves(root.lc);
printLeaves(root.rc);
}
}
public void connectToRightPointer(Node root){
if(root!=null){
Node tempLeft=root.lc;
if(tempLeft!=null){
if(root.rc!=null)
tempLeft.next=root.rc;
else{
Node dummy=root.next;
while(dummy.lc!=null||dummy.rc!=null){
dummy=dummy.next;
}
if(dummy.lc!=null)root.lc.next=dummy.lc;
else root.rc.next=dummy.rc;
}
}
if(root.rc!=null && root.next!=null){
root.rc.next=root.next.lc;
}
connectToRightPointer(root.lc);
connectToRightPointer(root.rc);
}
}
private List<Integer> treeViewList = new ArrayList<>();
public void leftTreeView(Node root,int size){
if(null!=root){
if(size>=treeViewList.size()){
treeViewList.add(root.data);
System.out.println(root.data + " ");
int tempSize=treeViewList.size();
leftTreeView(root.lc,tempSize);
leftTreeView(root.rc,tempSize);
}
}
}
public Node largestNumberNode(Node root) {
if (root != null) {
if (root.rc != null) {
root = largestNumberNode(root.rc);
} else {
return root;
}
}
return root;
}
public Node deleteNode(Node root, int num) {
if (root != null) {
if (num < root.data) {
root.lc = deleteNode(root.lc, num);
} else if (num > root.data) {
root.rc = deleteNode(root.rc, num);
} else if (num == root.data) {
// case 1: if node has no child
if (root.lc == null && root.rc == null) {
root = null;
}
// case 2: if node has 1 child
else if (root.lc == null && root.rc != null) {
root = root.rc;
// return root;
} else if (root.lc != null && root.rc == null) {
root = root.lc;
// return root;
}
// case 3: if node has two child
else if (root.lc != null && root.rc != null) {
// get the largest of left side node and copy to root
Node largestNumberNode = largestNumberNode(root.lc);
root.data = largestNumberNode.data;
// now delete the largest node
root.lc = deleteNode(root.lc, largestNumberNode.data);
// we can also get the smallest of right side and copy to
// root and repeat the same proccess.
}
}
}
return root;
}
/*
public boolean isSubTree(Node parent, Node child){
}
*/
public Node search(Node root,int data){
Node result=null;
if(root!=null){
if(data==root.data) result=root;
else if(data>root.data){
return search(root.rc,data);
}
else{
return search(root.lc,data);
}
return result;
}
else return result;
}
public boolean isBSTBalanced(Node root){
if(null==root) return true;
int leftHeight= getMaxDepth(root.lc);
int rightHeight= getMaxDepth(root.rc);
if(Math.abs(leftHeight-rightHeight)>1){
return false;
}
else{
return isBSTBalanced(root.lc) && isBSTBalanced(root.rc);
}
}
/*
public List<Node> combinationBST(int start, int end){
List<Node> result= new ArrayList<>();
for(int i=start;i<end;i++){
if(start>end){
result.add(null);
return result;
}
List<Node> left= showMessage(start,)
}
}
*/
public boolean pathSum(Node root, int sum, List<Node> path){
if(root==null) { return false;}
if(sum-root.data==0){
if(root.lc==null && root.rc==null){
path.add(root);
return true;
}
}
else{
if(pathSum(root.lc,sum-root.data,path)){
path.add(root);
return true;
}
if(pathSum(root.rc,sum-root.data,path)){
path.add(root);
return true;
}
}
return false;
}
public void insert(Node root, int data) {
if (data <= root.data) {
if (root.lc != null) {
insert(root.lc, data);
} else {
root.lc = new Node(data);
}
} else if (data > root.data) {
if(root.rc!=null){
insert(root.rc,data);
}
else{
root.rc=new Node(data);
}
}
}
//List<Integer> preOrder = new ArrayList<>();
public void preOrder(Node root) {
if (root != null) {
System.out.println(root.data);
//preOrder.add(root.data);
preOrder(root.lc);
preOrder(root.rc);
}
}
public void inOrder(Node root){
if(root!=null){
inOrder(root.lc);
System.out.print(root.data+" ");
inOrder(root.rc);
}
}
public void inOrderIteration(Node root){
Stack<Node> stack = new Stack<Node>();
if(root!=null)
stack.push(root);
while(!stack.isEmpty()) {
if (root != null) {
stack.push(root);//push element in stack
root = root.lc;//move to left
}
else{
root=stack.pop();//popping is done when left has ended
System.out.print(root.data+ " ");//print root
root=root.rc;//move to right
}
}
}
public void postOrder(Node root){
if(root!=null){
postOrder(root.lc);
postOrder(root.rc);
System.out.println(root.data+" ");
}
}
/**
* pass the storin gArray size 2^(height of tree + 1) -1
* to contain all values including leave node's child's null value
*
* pass initial parameter pos as 0
*/
public void serialize(Node root,int pos,Integer [] storingArray){
if(root==null){
storingArray[pos]=-1;
}
else{
storingArray[pos]=root.data;
serialize(root.lc,pos*2+1,storingArray);
serialize(root.rc,pos*2+2,storingArray);
}
}
public void deserialize(Integer[] storingArray,int pos,Node node){
if(storingArray[pos]==-1||pos>storingArray.length-1){
node=null;
}
else{
if(node==null) node = new Node(storingArray[pos]);
deserialize(storingArray,pos*2+1,node.lc);
deserialize(storingArray,pos*2+2,node.rc);
}
}
Map<Integer,Integer> levelContainer= new TreeMap<>();
public void topViewHelper(Node root,int level){
if(root!=null){
if(!levelContainer.containsKey(level)){
levelContainer.put(level,root.data);
}
topViewHelper(root.lc,level-1);
topViewHelper(root.rc,level+1);
}
}
public void bottomViewHelper(Node root,int level){
if(root!=null){
// if(!levelContainer.containsKey(level)){
levelContainer.put(level,root.data);
// }
bottomViewHelper(root.lc,level-1);
bottomViewHelper(root.rc,level+1);
}
}
public void topView(Node root){
topViewHelper(root,0);
for(int key:levelContainer.keySet()){
System.out.println(levelContainer.get(key)+" ");
}
}
public void bottomView(Node root){
bottomViewHelper(root,0);
for(int key:levelContainer.keySet()){
System.out.println(levelContainer.get(key)+" ");
}
}
public int diameter(Node root){
if(root!=null){
int leftHeight= getMaxDepth(root.lc);
int rightHeight = getMaxDepth(root.rc);
int leftDiameter = diameter(root.lc);
int rightDiameter = diameter(root.rc);
return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter));
}
return 0;
}
public Node sortedArrayToBST(int[] array,int low, int high){
if(array.length<1 ||low==high)return null;
int mid=(low+high)/2;
Node root=new Node(array[mid]);
root.lc=sortedArrayToBST(array,low,mid);
root.rc=sortedArrayToBST(array,mid+1,high);
return root;
}
public int getLevel(Node root,int a, int level){
if(root==null) return -1;
if(a==root.data) return level;
else{
int levelLeft=getLevel(root.lc,a,level+1);
int levelRight=getLevel(root.rc,a,level+1);
if(levelLeft!=-1) return levelLeft;
else return levelRight;
}
}
public boolean isCousin(Node root, int a, int b){
if(root==null) return false;
return getLevel(root,a,0)==getLevel(root,b,0) && !isSibling(root,a,b);
}
