BinaryTree

package testrun;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.TreeMap;

public class BinaryTree {
    public static int maxLevel = -1;
    public static int maxSum   = 0;

    public static Integer maxPathSum(Node root) {

        maxSumUtil(root);
        return maxSum;
    }

    public static Integer maxSumUtil(Node root) {
        if (root == null) {
            return 0;
        }
        int l = maxSumUtil(root.left);
        int r = maxSumUtil(root.right);
        int max1 = Math.max(Math.max(l, r) + root.data, root.data);
        int max2 = Math.max(max1, l + r + root.data);
        maxSum = Math.max(maxSum, max2);
        return max1;
    }

    public static void main(String[] arg) {

        /* Let us construct the tree shown in above diagram */
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(4);
        root.left.right = new Node(12);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        Node target = root.left.right;
        printNodesAtKthDisttanceFromGivenNode(root, target, 2);

        // timeToBurnTreeFromGivenNode(root, 25);
        // Node parent = findLCA(root, 3, 4);
        // System.out.println("Parent of 3 and 4 is: " + parent.data);
        //
        // int height = height(root, 0);
        // System.out.println("height: " + height);
        // System.out.println("Left view of tree is");
        // printLeftView(root, 0);
        // maxLevel = -1;
        // System.out.println("right view of tree is");
        // printRightView(root, 0);
        // val = new Values();
        // printVerticalOrderByMap(root);
        // printTopView(root);
        // prinBottomView(root);
        // printLevelOrder(root);
        // printLevelOrderSpiralWith2Stacks(root);
        // convertTreeToDLL(root);
        // int norOfLeaves = getNoOfLeafNodes(root);
        // System.out.print("No of leaves: " + norOfLeaves);
    }

    public static class Sum {
        int sum = 0;
    }

    static void printkdistanceNodeDown(Node node, int k) {
        if (node == null || k < 0)
            return;

        if (k == 0) {
            System.out.print(node.data);
            System.out.println("");
            return;
        }

        // Recur for left and right subtrees
        printkdistanceNodeDown(node.left, k - 1);
        printkdistanceNodeDown(node.right, k - 1);
    }

    public static int printNodesAtKthDisttanceFromGivenNode(Node node, Node targetNode, int k) {
        if (node == null) {
            return -1;
        }
        // if target is same as root,only print node down at distance k
        if (node == targetNode) {
            printkdistanceNodeDown(node, k);
            return 0;
        }
        int distanceFromLeft = printNodesAtKthDisttanceFromGivenNode(node.left, targetNode, k);
        if (distanceFromLeft != -1) {
            // here node found in left tree
            if (distanceFromLeft + 1 == k) {
                System.out.print(node.data);
                System.out.println("");
            } else {
                // else go to right tree with k-distanceinleft-2;
                printkdistanceNodeDown(node.right, k - distanceFromLeft - 2);
            }
            return 1 + distanceFromLeft;
        }
        int distanceFromRight = printNodesAtKthDisttanceFromGivenNode(node.right, targetNode, k);
        if (distanceFromRight != -1) {
            // here node found in left tree
            if (distanceFromRight + 1 == k) {
                System.out.print(node.data);
                System.out.println("");
            } else {
                // else go to left tree with k-distanceFromRight-2;
                printkdistanceNodeDown(node.left, k - distanceFromRight - 2);
            }
            return 1 + distanceFromRight;
        }
        return -1;
    }

    public static void sumOFSmallesetKthNodeInBST(Node root, int k, int count, Sum sum) {
        if (root == null) {
            return;
        }
        sumOFSmallesetKthNodeInBST(root.left, k, count + 1, sum);
        if (count < k) {
            sum.sum += root.data;
        }
        sumOFSmallesetKthNodeInBST(root.right, k, count + 1, sum);
    }

    public static boolean isHeightBalanced(Node root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(height(root.left) - height(root.right)) <= 1 && isHeightBalanced(root.left)
                && isHeightBalanced(root.right)) {
            return true;
        }
        return false;
    }

    public boolean checkBSTUtil(Node root, int min, int max) {
        if (root == null) {
            return true;
        }
        if (root.data < min || root.data > max) {
            return false;
        }
        return checkBSTUtil(root.left, min, root.data - 1) && checkBSTUtil(root.right, root.data + 1, max);
    }

    public static class Values {
        int min, max;
    }

    public static class Queue {
        Node node;
        int  level;

        public Queue(Node node, int level) {
            super();
            this.node = node;
            this.level = level;
        }
    }

    public static void printTopView(Node root) {
        System.out.println("Top view of tree");
        Queue queue = new Queue(root, 0);
        // tree map taken as we need in sorted order of horizontal distance
        Map<Integer, Node> map = new TreeMap<Integer, BinaryTree.Node>();
        LinkedList<Queue> q = new LinkedList<BinaryTree.Queue>();
        q.add(queue);
        while (!q.isEmpty()) {
            Queue curNode = q.poll();
            if (curNode != null) {
                if (!map.containsKey(curNode.level)) {
                    map.put(curNode.level, curNode.node);
                }
                if (curNode.node.left != null) {
                    q.add(new Queue(curNode.node.left, curNode.level - 1));
                }
                if (curNode.node.right != null) {
                    q.add(new Queue(curNode.node.right, curNode.level + 1));
                }
            }
        }
        for (int key : map.keySet()) {
            System.out.print(map.get(key).data + ",");
        }

    }

    public static void prinBottomView(Node root) {
        System.out.println("Bottom view of tree");
        Queue queue = new Queue(root, 0);
        // tree map taken as we need in sorted order of horizontal distance
        Map<Integer, Node> map = new TreeMap<Integer, BinaryTree.Node>();
        LinkedList<Queue> q = new LinkedList<BinaryTree.Queue>();
        q.add(queue);
        while (!q.isEmpty()) {
            Queue curNode = q.poll();
            if (curNode != null) {
                // replace node everytime we get a new one at given level as we
                // nned last one from particulat HD
                map.put(curNode.level, curNode.node);
                if (curNode.node.left != null) {
                    q.add(new Queue(curNode.node.left, curNode.level - 1));
                }
                if (curNode.node.right != null) {
                    q.add(new Queue(curNode.node.right, curNode.level + 1));
                }
            }
        }
        for (int key : map.keySet()) {
            System.out.print(map.get(key).data + ",");
        }

    }

    public static void getMinMaxHorizontalDistances(Node root, Values min, Values max, int hd) {
        if (root == null) {
            return;
        }
        if (hd < min.min) {
            min.min = hd;
        } else if (hd > max.max) {
            max.max = hd;
        }
        getMinMaxHorizontalDistances(root.left, min, max, hd - 1);
        getMinMaxHorizontalDistances(root.right, min, max, hd + 1);
    }

    public static void printVerticalLineWiseNodes(Node root, int curLine, int hd) {
        if (root == null) {
            return;
        }
        if (curLine == hd) {
            System.out.print(root.data + ",");
        }

        printVerticalLineWiseNodes(root.left, curLine, hd - 1);
        printVerticalLineWiseNodes(root.right, curLine, hd + 1);

    }

    public static void printVerticalOrder(Node root, Values val) {
        getMinMaxHorizontalDistances(root, val, val, 0);
        for (int curHD = val.min; curHD <= val.max; curHD++) {
            printVerticalLineWiseNodes(root, curHD, 0);
            System.out.println("");
        }
    }

    public static void populateMap(Node root, TreeMap<Integer, List<Node>> map, int hd) {
        if (root == null) {
            return;
        }
        if (map.containsKey(hd)) {
            map.get(hd).add(root);
        } else {
            List<Node> list = new ArrayList<BinaryTree.Node>();
            list.add(root);
            map.put(hd, list);
        }
        populateMap(root.left, map, hd - 1);
        populateMap(root.right, map, hd + 1);
    }

    public static void printVerticalOrderByMap(Node root) {
        TreeMap<Integer, List<Node>> map = new TreeMap<Integer, List<Node>>();
        populateMap(root, map, 0);
        for (int key : map.keySet()) {
            for (Node node : map.get(key)) {
                System.out.print(node.data + ",");
            }
            System.out.println("");
        }
    }

    public static int height(Node root) {
        if (root == null) {
            return -1;
        }
        int lh = height(root.left);
        int rh = height(root.right);
        return Math.max(lh, rh) + 1;
    }

    public static void printLeftView(Node root, int level) {
        if (root == null) {
            return;
        }
        if (level > maxLevel) {
            System.out.println(root.data);
            maxLevel = level;
        }

        printLeftView(root.left, level + 1);
        printLeftView(root.right, level + 1);
    }

    public static void printRightView(Node root, int level) {
        if (root == null) {
            return;
        }
        if (level > maxLevel) {
            System.out.println(root.data);
            maxLevel = level;
        }

        printRightView(root.right, level + 1);
        printRightView(root.left, level + 1);
    }

    public static void printLevelOrder(Node root) {
        LinkedList<Node> queue = new LinkedList<BinaryTree.Node>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            if (curNode != null) {
                System.out.print(curNode.data + " ");
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
        }
    }

    public static boolean areMirror(Node root1, Node root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if ((root1 == null && root2 != null) || (root1 != null && root2 == null)) {
            return false;
        }

        java.util.Queue<Node> queue = new LinkedList<BinaryTree.Node>();
        queue.add(root1);
        queue.add(root2);

        while (!queue.isEmpty()) {
            Node a = queue.peek();
            queue.poll();
            Node b = queue.peek();
            queue.poll();
            if (a.data != b.data) {
                return false;
            }
            if (a.left != null && b.right != null) {
                queue.add(a.left);
                queue.add(b.right);
            }
            if (a.left != null || b.right != null) {
                return false;
            }
            if (a.right != null && b.left != null) {
                queue.add(a.right);
                queue.add(b.left);
            }
            if (a.right != null || b.left != null) {
                return false;
            }
        }

        return true;
    }

    public static void printLevelOrderSpiralWith2Stacks(Node root) {
        Stack<Node> s1 = new Stack<BinaryTree.Node>();
        Stack<Node> s2 = new Stack<BinaryTree.Node>();
        s1.add(root);
        while (!s1.isEmpty() || !s2.isEmpty()) {
            while (!s1.isEmpty()) {
                Node curTop = s1.peek();
                s1.pop();
                System.out.print(curTop.data + ",");
                if (curTop.right != null) {
                    s2.add(curTop.right);
                }
                if (curTop.left != null) {
                    s2.add(curTop.left);
                }
            }
            while (!s2.isEmpty()) {
                Node curTop = s2.peek();
                s2.pop();
                System.out.print(curTop.data + ",");
                if (curTop.left != null) {
                    s1.add(curTop.left);
                }
                if (curTop.right != null) {
                    s1.add(curTop.right);
                }
            }
        }
    }

    public void connectNodesAtSameLevel(Node root) {
        java.util.Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        q.add(null);
        while (!q.isEmpty()) {
            Node curNode = q.peek();
            q.remove();
            if (curNode != null) {
                curNode.next = q.peek();

                if (curNode.left != null) {
                    q.add(curNode.left);
                }
                if (curNode.right != null) {
                    q.add(curNode.right);
                }
            }
            if (!q.isEmpty()) {
                q.add(null);
            }
        }
    }

    public static Node bintree2listUtil(Node node) {
        if (node == null)
            return node;

        if (node.left != null) {
            Node left = bintree2listUtil(node.left);
            for (; left.right != null; left = left.right)
                ;
            left.right = node;
            node.left = left;
        }

        if (node.right != null) {
            Node right = bintree2listUtil(node.right);
            for (; right.left != null; right = right.left)
                ;
            right.left = node;
            node.right = right;
        }
        return node;
    }

    public static Node convertTreeToDLL(Node root) {
        System.out.println("DLL:");
        if (root == null) {
            return root;
        }
        Node node = bintree2listUtil(root);
        while (node.left != null) {
            node = node.left;
        }
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.right;
        }
        return node;
    }

    public static boolean isIdenticalTreeRecursive(Node root1, Node root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 != null && root2 != null) {
            return root1.data == root2.data && isIdenticalTreeRecursive(root1.left, root2.left)
                    && isIdenticalTreeRecursive(root1.right, root2.right);
        }
        return false;
    }

    public static boolean isSubTree(Node bigTree, Node smallTree) {
        if (bigTree == null) {
            return false;
        }
        if (smallTree == null) {
            return true;
        }
        boolean isSame = isIdenticalTreeRecursive(bigTree, smallTree);
        if (isSame) {
            return true;
        }

        return isSubTree(bigTree.left, smallTree) || isSubTree(bigTree.right, smallTree)
                || isSubTree(bigTree, smallTree);

    }

    public static boolean isIdenticalIterative(Node root1, Node root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        java.util.Queue<Node> queue1 = new LinkedList<BinaryTree.Node>();
        java.util.Queue<Node> queue2 = new LinkedList<BinaryTree.Node>();
        queue1.add(root1);
        queue2.add(root2);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            Node n1 = queue1.peek();
            Node n2 = queue2.peek();
            queue1.remove();
            queue2.remove();
            if (n1 != null && n2 != null) {
                if (n1.data != n2.data) {
                    return false;
                }
                if (n1.left != null && n2.left != null) {
                    queue1.add(n1.left);
                    queue2.add(n2.left);
                }
                if (n1.left != null || n2.left != null) {
                    return false;
                }
                if (n1.right != null && n2.right != null) {
                    queue1.add(n1.right);
                    queue2.add(n2.right);
                }
                if (n1.right != null || n2.right != null) {
                    return false;
                }
            }
        }
        return true;
    }

    public int getDiameterN2(Node root) {
        if (root == null) {
            return 0;
        }
        int lH = height(root.left);
        int rH = height(root.right);
        int leftD = getDiameterN2(root.left);
        int rightD = getDiameterN2(root.right);
        return Math.max(Math.max(leftD, rightD), (lH + rH + 1));
    }

    public static class Height {
        int h;
    }

    public static int diameterWithCalculateHeightRecurs(Node root, Height height) {
        Height lh = new Height(), rh = new Height();
        if (root == null) {
            height.h = 0;
            return 0;
        }
        int leftDia = diameterWithCalculateHeightRecurs(root.left, lh);
        int rightDia = diameterWithCalculateHeightRecurs(root.right, rh);
        height.h = Math.max(lh.h, rh.h) + 1;
        return Math.max(Math.max(leftDia, rightDia), lh.h + rh.h + 1);
    }

    public static int getNoOfLeafNodes(Node root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getNoOfLeafNodes(root.left) + getNoOfLeafNodes(root.right);
    }

    public static int rootToLeafMaxSum(Node root) {
        if (root == null) {
            return 0;
        }
        int leftSum = rootToLeafMaxSum(root.left);
        int rightSum = rootToLeafMaxSum(root.right);
        return Math.max(leftSum, rightSum) + root.data;
    }

    public static void diagonalTraversalRecursiveUtil(Node root, HashMap<Integer, List<Integer>> map, int distance) {
        if (root == null) {
            return;
        }
        if (map.containsKey(distance)) {
            map.get(distance).add(root.data);
        } else {
            List<Integer> list = new ArrayList<Integer>();
            list.add(root.data);
            map.put(distance, list);
        }
        // vertical distance increases for left child
        diagonalTraversalRecursiveUtil(root.left, map, distance + 1);
        // vertical distance remains same for right child
        diagonalTraversalRecursiveUtil(root.right, map, distance);
    }

    public static void diagonalTraversalRecursive(Node root) {
        HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        diagonalTraversalRecursiveUtil(root, map, 0);
        for (Entry<Integer, List<Integer>> entry : map.entrySet()) {
            for (int i : entry.getValue()) {
                System.out.print(i + "-");
            }
            System.out.println();
        }

    }

    public static void diagonalTraversalIterative(Node root) {
        // maintain a queue for right tree

        java.util.Queue<Node> queue = new LinkedList<BinaryTree.Node>();
        queue.add(root);
        // add a delimiter to get the end of current diagonal
        queue.add(null);
        while (!queue.isEmpty()) {
            Node curNode = queue.peek();
            queue.remove();
            // if delimiter reaches means end of current diagonal insert new
            // delimiter and print new line
            if (curNode == null) {
                if (queue.size() == 0) {
                    return;
                }
                System.out.println();
                queue.add(null);
            } else {
                while (curNode != null) {
                    System.out.print(curNode.data + "-");
                    // if left child is present
                    // add into queue
                    if (curNode.left != null) {
                        queue.add(curNode.left);
                    }

                    curNode = curNode.right;
                }
            }
        }
    }

    public static void preOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);

    }

    public static void postOrder(Node root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.data + " ");
    }

    public static void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.data + " ");
        inOrder(root.right);
    }

    static void swapEveryKLevelUtil(Node root, int level, int k) {
        if (root == null || (root.left == null && root.right == null))
            return;

        if ((level + 1) % k == 0) {
            Node temp = root.left;
            root.left = root.right;
            root.right = temp;
        }

        swapEveryKLevelUtil(root.left, level + 1, k);
        swapEveryKLevelUtil(root.right, level + 1, k);
    }

    public static void huffmanEncoding() {
        char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' };
        int[] charfreq = { 5, 9, 12, 13, 16, 45 };
        PriorityQueue<Node> minHeap = new PriorityQueue<Node>(6, new HuffManComparatort());

        // create a min heap for characters
        for (int index = 0; index < charArray.length; index++) {
            Node n = new Node(charfreq[index]);
            n.c = charArray[index];
            n.left = n.right = null;
            minHeap.add(n);
        }
        Node root = null;
        // traverse the heap till single node remaining and extract first
        // two,sum it and make them left and right child to new node ,insert
        // into min heap again
        while (minHeap.size() > 1) {
            Node firstNode = minHeap.peek();
            minHeap.remove();
            Node secondNode = minHeap.peek();
            minHeap.remove();

            int newData = firstNode.data + secondNode.data;
            Node temp = new Node(newData);
            temp.left = firstNode;
            temp.right = secondNode;
            temp.c = '-';
            root = temp;
            minHeap.add(temp);
        }
        // print the huffman encoding
        printHuffmanEncoding(root, "");

    }

    public static void printHuffmanEncoding(Node root, String s) {
        if (root.left == null && root.right == null && Character.isLetter(root.c)) {
            System.out.println(root.c + ":" + s);
            return;
        }
        printHuffmanEncoding(root.left, s + "0");
        printHuffmanEncoding(root.right, s + "1");

    }

    static class HuffManComparatort implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return o1.data - o2.data;
        }

    }

    public static Node removeLeavesAtLevellessThanK(Node root, int level, int k) {
        if (root == null) {
            return null;
        }
        root.left = removeLeavesAtLevellessThanK(root.left, level + 1, k);
        root.right = removeLeavesAtLevellessThanK(root.right, level + 1, k);

        if (root.left == null && root.right == null && level < k) {
            root = null;
        }
        return root;
    }

    public static class Level {
        int maxlevel = 0;
    }

    static Node deepestLeaf = null;

    public static void deepestLeafNodeInTree(Node root, int curLevel, Level level) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null && curLevel > level.maxlevel) {
            level.maxlevel = curLevel;
            deepestLeaf = root;
        }
        deepestLeafNodeInTree(root.left, curLevel + 1, level);
        deepestLeafNodeInTree(root.right, curLevel + 1, level);
    }

    public static int getLevelOfKey(Node root, int key, int level) {
        if (root == null) {
            return -1;
        }
        if (root.data == key) {
            return level;
        }
        int l = getLevelOfKey(root.left, key, level + 1);
        return (l == -1 ? getLevelOfKey(root.right, key, level + 1) : l);
    }

    public static Node findLCA(Node root, int first, int second) {
        if (root == null) {
            return null;
        }
        if (root.data == first || root.data == second) {
            return root;
        }
        Node retLeft = findLCA(root.left, first, second);
        Node retRight = findLCA(root.right, first, second);
        if (retLeft != null && retRight != null) {
            return root;
        }
        return retLeft != null ? retLeft : retRight;
    }

    public static void timeToBurnTreeFromGivenNode(Node root, int dataOfGiveNode) {
        int levelOfKeyInleftTree = getLevelOfKey(root.left, dataOfGiveNode, 1);
        int levelOfKeyInRightTree = getLevelOfKey(root.right, dataOfGiveNode, 1);
        Level levelOfDeepestLeaf = new Level();
        int depthOfStartingNode = -1;
        int depthOfLeafNodeAtSameSide = -1;
        int depethOfOppositeSide = -1;
        int depthOfCommonAncestor = -1;
        // starting node found in left tree,Found the deepest leaf from left
        // tree else do the same in right tree
        if (levelOfKeyInleftTree > 0) {
            depthOfStartingNode = levelOfKeyInleftTree;
            deepestLeafNodeInTree(root.left, 1, levelOfDeepestLeaf);
            depethOfOppositeSide = height(root.right) + 1;
        } else if (levelOfKeyInRightTree > 0) {
            depthOfStartingNode = levelOfKeyInRightTree;
            deepestLeafNodeInTree(root.right, 1, levelOfDeepestLeaf);
            depethOfOppositeSide = height(root.left) + 1;
        }
        System.out.println("depthOfStartingNode: " + depthOfStartingNode);
        System.out.println("depethOfOppositeSide: " + depethOfOppositeSide);
        System.out.println("depthOfLeafNodeAtSameSide: " + levelOfDeepestLeaf.maxlevel);
        if (deepestLeaf != null) {
            depthOfLeafNodeAtSameSide = levelOfDeepestLeaf.maxlevel;
            // find common ancestor of starting node and deepest leaf of same
            // side
            Node commonAncestor = findLCA(root, dataOfGiveNode, deepestLeaf.data);
            System.out.println("commonAncestor: " + commonAncestor.data);
            depthOfCommonAncestor = getLevelOfKey(root, commonAncestor.data, 0);
            System.out.println("depthOfCommonAncestor: " + depthOfCommonAncestor);
        }
        int timeToBurn = Math.max(
                ((depthOfLeafNodeAtSameSide - depthOfCommonAncestor) + (depthOfStartingNode - depthOfCommonAncestor)),
                (depthOfStartingNode + depethOfOppositeSide));
        System.out.println("Time to burn tree: " + timeToBurn);

    }

    public static class Node {
        Node left;
        Node right;
        int  data;
        Node next;
        char c;

        Node(int key) {
            this.data = key;
            left = null;
            right = null;
        }

        public Node(Node left, Node right, int data) {
            super();
            this.left = left;
            this.right = right;
            this.data = data;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

    }

}