Boundary traversal of binary tree (Border Elements)

public class PrintBoundryOftree {

    public static void main(String[] args) {
        int[] arr = {10, 5, 4, 7, 15, 14, 17};
        Node root = null;
        for (int val : arr) {
            root = insertNode(root, val);
        }
        printInorder(root);

        System.out.println("\n*** print boundry***\n");
        System.out.println("**print left**");
        printLeftBoundry(root);
        System.out.println("\n**print right boundry**\n");
        printRightBoundry(root.right); //start from right  due to root already cover in left boundry
        System.out.println("\n**leaf boundry**\n");
        printLeafBoundry(root);
    }

    static void printLeftBoundry(Node node) {
        if (null != node) {
            if (null != node.left) {
                System.out.println(node.value);
                printLeftBoundry(node.left);
            } else if (null != node.right) {
                System.out.println(node.value);
                printLeftBoundry(node.right);
            }
        }
    }

    static void printRightBoundry(Node node) {
        if (null != node) {
            if (null != node.right) {
                System.out.println(node.value);
                printRightBoundry(node.right);
            } else if (null != node.left) {
                System.out.println(node.value);
                printRightBoundry(node.left);
            }
        }
    }

    static void printLeafBoundry(Node node) {
        if (null != node) {
            printLeafBoundry(node.left);
            if (null == node.left && null == node.right) {
                System.out.println(node.value);
            }
            printLeafBoundry(node.right);

        }
    }

    static void printInorder(Node root) {
        if (null != root) {
            printInorder(root.left);
            System.out.println(root.value);
            printInorder(root.right);
        } else {
            return;
        }

    }

    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
            } else {
                root.right = insertNode(root.right, value);
            }
            return root;
        }

    }

    static class Node {

        Integer value;
        Node left;
        Node right;

        Node(Integer value) {
            this.value = value;
            left = right = null;
        }
    }
}

output:
**original**
4
5
7
10
14
15
17

*** print boundry***

**print left**
10
5

**print right**

15

**left**

4
7
14
17

Ref: https://www.youtube.com/watch?v=uemjIijtu2I

Print Diagonal of Binary tree and their sum

package tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class PrintDiagonalBinaryTree {
    public static void main(String[] args) {
       
        int[] arr = {10,5,4,7,15,14,17};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
         printInorder(root);
         System.out.println("\n*****print diagonl****\n");
         printDiagnol(root);
       
    }
    static void printInorder(Node root) {
        if(null!=root) {
            printInorder(root.left);
            System.out.println(root.value);
            printInorder(root.right);
        }else {
            return;
        }
       
    }
   
    static void printDiagnol(Node root) {
        Map<Integer, Integer> map = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        queue.add(null);
        Node p=null;
        int count = 0;
        while(!queue.isEmpty()) {
            p = queue.remove();
            if(p==null) {
                count = count+1;
                queue.add(null);
                p = queue.remove();
                if(null==p) {
                    break;
                }
            }
            System.out.println("diagnol::"+count);
            while(null!=p) {
                System.out.println(p.value);
                if(map.containsKey(count)) {
                    map.put(count, map.get(count)+p.value);
                }else {
                    map.put(count, p.value);
                }
                if(null!=p.left) {
                    queue.add(p.left);
                }
                p = p.right;
            }
        }
        System.out.println("\n***print sum of each diagonal***\n");
        map.forEach((k,v)-> {
            System.out.println("diagonal ::"+k+" sum is::"+v);
        });
    }
   
    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
            } else {
                root.right = insertNode(root.right, value);
            }
            return root;
        }

    }
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
}
output:
**origianl**
4
5
7
10
14
15
17

*****print diagonl****

diagnol::0
10
15
17
diagnol::1
5
7
diagnol::1
14
diagnol::2
4

***print sum of each diagonal***

diagonal ::0 sum is::42
diagonal ::1 sum is::26
diagonal ::2 sum is::4

Note: the reason behind adding null in queue to trigger end of a diagonal.
main logic: find diagonal using distance start from root d=0 and d=parent+1(for left sub tree) and d= parent(for right sub tree).


Ref: https://www.youtube.com/watch?v=e9ZGxH1y_PE

RecoverBinarySearchTree

public class RecoverBinarySearchTree {
    static Node temp1;
    static Node temp2;
    static Node previousNode=null,firstStartNode=null,LastEndNode=null;
    public static void main(String[] args) {
        int[] arr = {10,5,4,7,15,14,17};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
         System.out.println("*****************original***********");
         printInorder(root);
         temp1.value = 15; //replace from 5
         temp2.value = 5; //replace from 15
         System.out.println("*****************after replace***********");
         printInorder(root);
       
         System.out.println("*****************recover***********");
         findSegments(root);
         int val = firstStartNode.value;
         firstStartNode.value = LastEndNode.value;
         LastEndNode.value = val;
         printInorder(root);
       
       
    }
   
    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
                if(root.left.value==5) {
                    temp1 = root.left;
                }
                if(root.left.value==15) {
                    temp2 = root.left;
                }
            } else {
                root.right = insertNode(root.right, value);
                if(root.right.value==5) {
                    temp1 = root.right;
                }
                if(root.right.value==15) {
                    temp2 = root.right;
                }
            }
           
            return root;
        }

    }
   
   
    static void findSegments(Node root) {
        if(null==root) {
            return;
        }
        findSegments(root.left);
        //logic
        if(previousNode!=null) {
            if(previousNode.value>root.value) {
                if(null==firstStartNode) {
                    firstStartNode = previousNode;
                }
                LastEndNode = root;
            }
        }
        previousNode = root;
        findSegments(root.right);
    }
   
    static void printInorder(Node root) {
        if(null!=root) {
            printInorder(root.left);
            System.out.println(root.value);
            printInorder(root.right);
        }else {
            return;
        }
       
    }
   
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
}
output:
*****************original***********
4
5
7
10
14
15
17
*****************after replace***********
4
15
7
10
14
5
17
*****************recover***********
4
5
7
10
14
15
17

Get Minimum and maximum depth of Binary Tree

public class MinMaxDepthBT {
    public static void main(String[] args) {
        int[] arr = {5,3,8,2,1,6,7,4,9};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
       
       
          System.out.println(getMinLenthBT(root));
          System.out.println(getMaxLenthBT(root));
    }
   
    static void preorder(Node node) {
        if(null!=node) {
            System.out.println(node.value);
            preorder(node.left);
            preorder(node.right);
        }
    }
   
    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
            } else {
                root.right = insertNode(root.right, value);
            }
            return root;
        }

    }
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
   
    public static int getMinLenthBT(Node root) {
        if(null==root) {
            return 0;
        }
        if(root.left==null && root.right==null) {
            return 1;
        }
        int left = root.left!=null ? getMinLenthBT(root.left) : Integer.MAX_VALUE;
        int right = root.right!=null ? getMinLenthBT(root.right) : Integer.MAX_VALUE;
        return 1+Math.min(left, right);
    }
   
    public static int getMaxLenthBT(Node root) {
        if(null==root) {
            return 0;
        }
        if(root.left==null && root.right==null) {
            return 1;
        }
        int left = root.left!=null ? getMaxLenthBT(root.left) : Integer.MIN_VALUE;
        int right = root.right!=null ? getMaxLenthBT(root.right) : Integer.MIN_VALUE;
        return 1+Math.max(left, right);
    }
}
output: min 3 and max 4

Create a balanced Binary Search Tree (BST) from a sorted array

public class CreateBST {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
       
         Node node = createBST(arr, 0, arr.length-1);
         preorder(node);
    }
   
    static void preorder(Node node) {
        if(null!=node) {
            System.out.println(node.value);
            preorder(node.left);
            preorder(node.right);
        }
    }
   
    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
            } else {
                root.right = insertNode(root.right, value);
            }
            return root;
        }

    }
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
   
    static Node createBST(int[] arr,int start,int end) {
        if(start>end) {
            return null;
        }
        int mid = (start+end)/2;
        Node node = new Node(arr[mid]);
        node.left = createBST(arr, start, mid-1);
        node.right = createBST(arr, mid+1, end);
        return node;
    }
   
    }

LowestCommonAncesstor

public class LowestCommonAncesstor {
   
    public static void main(String[] args) {
        int[] arr = {3,6,5,9,2,8};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
       
         Node node = getLCA(root, 5, 8);//output 6
         System.out.println(node.value);
    }
   
    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
            } else {
                root.right = insertNode(root.right, value);
            }
            return root;
        }

    }
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
   
    static Node getLCA(Node currentNode,int A,int B) {
        if(currentNode==null) {
            return null;
        }
        if(currentNode.value==A || currentNode.value==B) {
            return currentNode;
        }
        Node left = getLCA(currentNode.left, A, B);
        Node right = getLCA(currentNode.right, A, B);
        if(null!=left && null!=right) {
            return currentNode;
        }
        if(null==left) {
            return right;
        }else {
            return left;
        }
    }
   
}