CareerCup

static int mixDif = Integer.MIN_VALUE;
public static int maxDifNodes(TreeNode root,TreeNode node){
        
        if(root==node){
            return 0;
        }
        
        inorder(root,node);
        return maxDif;
    }
    
    
    public static TreeNode inorder(TreeNode root,TreeNode node){
        if(root==null){
            return null;
        }
        if(root==node){
            
            maxDif = Math.max(maxDif,Math.abs(root.val-node.val));
            return node;
        }
        
        TreeNode left = inorder(root.left,node);
        TreeNode right = inorder(root.right,node);
        if(left==null&&right==null){
            return null;
        }else{
            maxDif = Math.max(maxDif,Math.abs(root.val-node.val));
            return node;
        }
    }

package random;

import java.util.HashMap;
import java.util.Map;

public class MaxDiffTree {

    public static void main(String[] args) {

        TreeNode leafOne = new TreeNode(2, null, null);
        TreeNode leafTwo = new TreeNode(3, null, null);
        TreeNode oneLevelOne = new TreeNode(5, leafOne, leafTwo);
        TreeNode root = new TreeNode(2, oneLevelOne, null);

        MaxDiffTree maxDiffTreeSolver = new MaxDiffTree();
        System.out.println(maxDiffTreeSolver.findMaxDiff(root));

    }

    public int findMaxDiff(TreeNode root) {
        if (root == null) {
            System.out.println("don't fuck with me");
            return -1;
        }

        Integer currentBest = -2;
        Map<TreeNode, Integer> maxMap = new HashMap<>();
        Map<TreeNode, Integer> minMap = new HashMap<>();

        createMaxMap(root, maxMap);
        createMinMap(root, minMap);
        currentBest = findMaxDifference(root, maxMap, minMap);
        System.out.println("Best difference is " + currentBest);
        return currentBest;
    }

    private int findMaxDifference(TreeNode node, Map<TreeNode, Integer> maxChild, Map<TreeNode, Integer> minChild) {

        int currentBest = -2;

        if (node.left != null) {
            currentBest = findMaxDifference(node.left, maxChild, minChild);
        }

        if (node.right != null) {
            currentBest = findMaxDifference(node.right, maxChild, minChild);
        }

        if (Math.abs(maxChild.get(node) - node.value) > currentBest) {
            currentBest = Math.abs(maxChild.get(node) - node.value);
        }
        if (Math.abs(node.value - minChild.get(node)) > currentBest) {
            currentBest = Math.abs(node.value - minChild.get(node));
        }
        return currentBest;

    }

    private int createMinMap(TreeNode node, Map<TreeNode, Integer> minMap) {
        int min = node.value;
        if (node.left != null) {
            int minLeft = createMinMap(node.left, minMap);
            if (minLeft < min) {
                min = minLeft;
            }
        }

        if (node.right != null) {
            int minRight = createMaxMap(node.right, minMap);
            if (minRight < min) {
                min = minRight;
            }
        }

        minMap.put(node, min);
        return min;
    }

    private int createMaxMap(TreeNode node, Map<TreeNode, Integer> maxMap) {
        int max = node.value;
        if (node.left != null) {
            int maxLeft = createMaxMap(node.left, maxMap);
            if (maxLeft > max) {
                max = maxLeft;
            }
        }

        if (node.right != null) {
            int maxRight = createMaxMap(node.right, maxMap);
            if (maxRight > max) {
                max = maxRight;
            }
        }

        maxMap.put(node, max);
        return max;
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public boolean isLeaf() {
        if (left == null && right == null) {
            return true;
        }
        return false;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.value = val;
        this.left = left;
        this.right = right;
    }
}

package random;

import java.util.HashMap;
import java.util.Map;

public class MaxDiffTree {

public static void main(String[] args) {

TreeNode leafOne = new TreeNode(2, null, null);
TreeNode leafTwo = new TreeNode(3, null, null);
TreeNode oneLevelOne = new TreeNode(5, leafOne, leafTwo);
TreeNode root = new TreeNode(2, oneLevelOne, null);

MaxDiffTree maxDiffTreeSolver = new MaxDiffTree();
System.out.println(maxDiffTreeSolver.findMaxDiff(root));

}

public int findMaxDiff(TreeNode root) {
if (root == null) {
System.out.println("don't fuck with me");
return -1;
}

Integer currentBest = -2;
Map<TreeNode, Integer> maxMap = new HashMap<>();
Map<TreeNode, Integer> minMap = new HashMap<>();

createMaxMap(root, maxMap);
createMinMap(root, minMap);
currentBest = findMaxDifference(root, maxMap, minMap);
System.out.println("Best difference is " + currentBest);
return currentBest;
}

private int findMaxDifference(TreeNode node, Map<TreeNode, Integer> maxChild, Map<TreeNode, Integer> minChild) {

int currentBest = -2;

if (node.left != null) {
currentBest = findMaxDifference(node.left, maxChild, minChild);
}

if (node.right != null) {
currentBest = findMaxDifference(node.right, maxChild, minChild);
}

if (Math.abs(maxChild.get(node) - node.value) > currentBest) {
currentBest = Math.abs(maxChild.get(node) - node.value);
}
if (Math.abs(node.value - minChild.get(node)) > currentBest) {
currentBest = Math.abs(node.value - minChild.get(node));
}
return currentBest;

}

private int createMinMap(TreeNode node, Map<TreeNode, Integer> minMap) {
int min = node.value;
if (node.left != null) {
int minLeft = createMinMap(node.left, minMap);
if (minLeft < min) {
min = minLeft;
}
}

if (node.right != null) {
int minRight = createMaxMap(node.right, minMap);
if (minRight < min) {
min = minRight;
}
}

minMap.put(node, min);
return min;
}

private int createMaxMap(TreeNode node, Map<TreeNode, Integer> maxMap) {
int max = node.value;
if (node.left != null) {
int maxLeft = createMaxMap(node.left, maxMap);
if (maxLeft > max) {
max = maxLeft;
}
}

if (node.right != null) {
int maxRight = createMaxMap(node.right, maxMap);
if (maxRight > max) {
max = maxRight;
}
}

maxMap.put(node, max);
return max;
}
}

class TreeNode {
int value;
TreeNode left;
TreeNode right;

public boolean isLeaf() {
if (left == null && right == null) {
return true;
}
return false;
}

public TreeNode(int val, TreeNode left, TreeNode right) {
this.value = val;
this.left = left;
this.right = right;
}
}

/*
* Traverse Tree
* Keep Track of MaxSoFar and MaxDiff
*
*/

public class BinaryTreeMaxDiffBetweenAndNodeAncestor {
	
	public static int getMaxDiffNodeAndAncestor(Node root, int maxSoFar, int maxDiff){
		if(root==null){
			return maxDiff;
		}else{
			maxDiff=Math.max(maxDiff, maxSoFar-root.data);
			maxSoFar=Math.max(maxSoFar, root.data);

			return Math.max(getMaxDiffNodeAndAncestor(root.leftChild,maxSoFar,maxDiff), 
					getMaxDiffNodeAndAncestor(root.rightChild, maxSoFar, maxDiff));
		}
		
	}
	
	public static void main(String[] args) {
		
		Node root = new Node(8);
		root.rightChild=new Node(10);
		root.rightChild.rightChild=new Node(14);
		root.rightChild.rightChild.leftChild=new Node(13);

		root.leftChild=new Node(3);
		root.leftChild.leftChild=new Node(1);
		
		root.leftChild.rightChild=new Node(6);
		root.leftChild.rightChild.rightChild=new Node(7);
		root.leftChild.rightChild.leftChild=new Node(4);
		
		int maxDiff = getMaxDiffNodeAndAncestor(root,0,0);
		System.out.println(maxDiff);
	}
	
	static class Node{
		int data;
		Node leftChild;
		Node rightChild;
		Node(int data){
			this.data = data;
		}
	}
}