Algorithm: Continue exploring Tree Structure

Given a Tree Node, find its direct successor based different Traversal Type

Pre-Order

this is the simplest case, if the node has left child, then this left child is its successor, otherwise its right child is its successor.

Mid-Order

• if current node has right child, then the successor is the left-most node on its right sub-tree.
• if current node doesn’t have right child, find its first ancestor whose left sub-tree containing current node

to simplify the problem I will use a customized Node in this problem

public class TreeNode {
    int val;
    
    TreeNode parent;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int val) {
        this.val = val;
    }
}

public class FindDirectSuccessor {
    public static TreeNode findDirectSuccessor(TreeNode cur) {
        if (cur.right != null) {
            return findLeftMostNode(cur);
        } else {
            TreeNode parent = cur.parent;
            while(parent != null && parent.left != cur) {
                cur = parent;
                parent = cur.parent;
            }
            return parent;
        }
    }
    
    private static TreeNode findLeftMostNode(TreeNode cur) {
        while(cur.left != null) {
            cur = cur.left;
        }
        
        return cur;
    }
    
}

Post-Order

• if current node is its parent’s right child, then its parent node is its successor
• if current node is its parent’s left child, then find the leftmost node of its parent right sub-tree

public class TreeNode {
    int val;
    
    TreeNode parent;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int val) {
        this.val = val;
    }
}

public class SuccessorFinder {
    public TreeNode findSuccessorInPostOrder(TreeNode cur) {
        TreeNode parent = cur.parent;
        if(parent == null) {
            return null;
        }
        
        if(cur == parent.right) {
            return parent;
        } else {
            if (parent.right == null) {
                return parent;
            } else {
                return findLeftMostNode(parent.right);
            }
        }
    }
    
    private TreeNode findLeftMostNode(TreeNode head) {
        while(head.left != null) {
            head = head.left;
        }
        
        return head;
    }
}

Find the biggest Binary Search Tree in a given tree

• leverage post-order traversal, understand if each child tree is BST, then collect and aggregate the result to report to upper level
• the information we need from each sub-tree
  • is the subtree a BST?
  • its biggest value
  • its smallest value
  • its size

// definition of tree node
public class Node {
    int val;
    
    Node left;
    Node right;
    
    public Node(int val) {
        this.val = val;
    }
}

public class Info {
    int max;
    int min;
    int size;
    boolean isBST;
    
    
    Node maxBSTHead;
    int maxBSTSize;
    
    public Info(...) {
        ...;
    }
}

public class BiggestBST {
    public static Node findBiggestBST(Node head) {
        Info info = process(head);
        
        return info.maxBSTHead;
    }
    
    public Info process(Node head) {
        if(head == null) {
            return null;
        }
        
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        
        boolean isBST = true;
        Node maxBSTHead;
        int maxBSTSize = 0;
        
        if (leftInfo != null) {
            isBST = isBST && leftInfo.isBST && leftInfo.max <= head.val;
           	maxBSTSize = leftInfo.maxBSTSize;
            maxBSTHead = leftInfo.maxBSTHead;
        }
        
        if(rightInfo != null) {
            isBST = isBST && rightInfo.isBST && rightInfo.min >= head.val;
            
            if (rightInfo.maxBSTSize > maxBSTSize) {
                maxBSTSize = rightInfo.maxBSTSize;
                maxBSTHead = rightInfo.maxBSTHead;
            }
        }
        
        int max = 0;
        int min = 0;
        int size = 1;
        
        if (isBST) {
            min = leftInfo.min;
            max = rightInfo.max;
            
            maxBSTSize = leftInfo.size + rightInfo.size + 1;
            maxBSTHead = head;
        }
        
        return new Info(min, max, isBST, maxBSTSize, maxBSTHead);
        
    }
}

Max Happy Sum

assume a company is going to have a party, the partitioners can be a manager or worker.

each people has a happy value.

constraints:

• if manager come to party, then his direct worker will not participate this party

given the CEO of company (root of the tree), calculate the biggest happy sum we can achieve.

// definition of node
public class Worker {
    int happy;
    
    List<Worker> workers;
}

then for each worker, there are two conditions we need to care about, come or not come

public class Info {
    int come;
    int notCome;
    
    public Info(int come, int notCome) {
        this.come = come;
        this.notCome = notCome;
    }
}

public class PartyMaxHappy {
    public static int getMaxHappy(Worker head) {
        Info info = process(head);
        
        return Math.max(head.come, head.notCome);
    }
    
    private static Info process(Worker head) {
        if (head == null) {
            return null;
        }
        
        Info cur = null;
        int come;
        int notCome;
        for(Worker worker: head.workers) {
            cur = process(worker);
            if (cur != null) {
                come += cur.notCome;
                notCome += Math.max(cur.come, cur.notCome);
            }
        }
        
        return new Info(come, notCome);
    }
}

Max Distance between two nodes

• on each node, gather its longest sub-tree path
• on each node ,gather the longest distance between the nodes on its subtree

public class LongestDistance {
    public static int findLongestDistance(Node node) {
        Info info = process(node);
        
        return info.longestPath;
    }
    
    private static Info process(Node node) {
        if (node == null) {
            return null;
        }
        
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        
        int depth = 0;
        int longestPath = 0;
        int curLength = 1;
        if (leftInfo != null) {
            depth = leftInfo.depth;
            curLength += leftInfo.depth;
            longestPath = leftInfo.longestPath;
        }
        
        if (rightInfo != null) {
            depth = Math.max(depth, rightInfo.depth);
            curLength += rightInfo.depth;
            longestPath = Math.max(longestPath, rightInfo.longestPath);
        }
        
        depth++;
        longestPath = Math.max(curLength, longestPath);
        
        return new Info(depth, longestPath);
    }
}

public class Info {
    int depth;
    int longestDistance;
    
    public Info(int depth, int longestDistance) {
        this.depth = depth;
        this.longestDistance = longestDistance;
    }
}

Verify if a tree is Binary Balanced Tree

what is Binary Balanced Tree?

1. difference between the left and the right subtree for any node is not more than one
2. the left subtree is balanced
3. the right subtree is balanced

public class BinaryBalancedTreeVerifier {
    public static boolean verify(Node head) {
        
    }
    
    private static Info process(Node node) {
        if (node == null) {
            return new Info(true, 0);
        }
        
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        
        boolean isBST = leftInfo.isBST && rightInfo.isBST && Math.abs(leftInfo.depth - rightInfo.depth) <= 1;
        int depth = 1 + Math.max()
    }
}

public class Info {
    boolean isBalanced;
    int depth;
    
    public Info(boolean isBalanced, int depth) {
        this.isBalanced = isBalanced;
        this.depth = depth;
    }
}