Tuesday, November 29, 2016

Binary Tree All Paths, Max Sum Path, Diameter, Longest Path, Shortest Path, Closest Leaf


http://www.zrzahid.com/binary-tree-all-paths-max-sum-path-diameter-longest-path-shortest-path-closest-leaf/
Given a Binary Tree T.
1. Find all paths from root to each of the leaves in T.
2. Find the longest path from root to a leaf (also called Max Depth or Height of the tree).
3. Find the path that has largest sum along the path in T.
4. Find distance (shortest) between given two nodes in T.
5. Diameter of T or Longest path between any two nodes in T.
6. Find mirror image tree of T.
7. Find min length path that sums to a given value.
8. Find the closest leaf from root.
For example, in the following
                1
              /   \
             2     3
            /    /   \
           4    5     6
            \        /
             7      8
1. All Paths – [1–>2–>4–>7, 1–>3–>5, 1–>3–>6–>8]
2. Longest path aka Max Depth aka height of the tree is 4 because of longest path [1–>2–>4–>7] or [1–>3–>6–>8]
3. Max sum path – 31 from path [7–>4–>2->1–>3–>6–>8]
4. Distance between Node 5 and Node 8 is 3.
5. Diameter of T is 7 because there are 7 nodes in the longest path between node 7 and node 8.
6. Mirror image tree of T is
                1
              /   \
             3     2
            / \     \
           6   5     4
            \        /
             8      7
7. Checkout previous post on Min len sum-path.
8. Closest leaf is 5 (1->3->5)
All Paths from Root to Leaves
We can do DFS traverse from root until we find a leaf node and print the path DFS traverse visited.
public static void paths(BTNode root, String path, ArrayList<String> paths){
  if(root == null){
   return;
  }
  
  path=path+(path.isEmpty()? "" : "-->")+root.key;
  
  if(root.left == null && root.right == null){
   System.out.println("path > "+path);
   paths.add(path);
   return;
  }
  
  paths(root.left, path, paths);
  paths(root.right, path, paths);
 }

Largest Sum Path
We can do a similar DFS traverse. let’s take a binary tree.
Screen Shot 2015-10-19 at 12.44.51 AM
Path with max sum can be formed by either –
1. Starting from one subtree of root and going through root to other subtree (path 1), or
2. Path that doesn't go through root i.e. it ends at root. We can have 2 such paths - 
     2.1. Paths completely in left subtree that ends at root (path 2)
     2.2. Paths completely in right subtree that ends at root (path 3)
So, at a node maximum path would be maximum of 3 paths (path1, path2, and path3). We can compute path2 and path3 by recursively in the respective subtrees. But how do we calculate path1 that spans across the left and right subtrees? Idea is that, as recursive calls to left and right sum will always return maximum of path2 or path3, so we can compute path1 using path2 and path3 recursively by updating a global max with the path1 computed.
path2 or path3 computed as follows - 
local_max(node) = max{local_max(node.left), local_max(node.right)} + node.key

Then , global maxima path at current node would be -

global_max = max{global_max, local_max(root.left)+local_max(root.left)+root.key}
public static int maxSumPath1(BTNode node, int[] maxSum){
  if(node ==  null){
   return 0;
  }
  
  int leftSum = maxSumPath(node.left, maxSum);
  int rightSum = maxSumPath(node.right, maxSum);
  
  //update global max so far
  //we take max by either going through current root or not going through
  //current root if we take root then the max sum path goes from a left 
  //subtree node through root to a right subtree node
  //if we don't take current root then we disregard path 
  //through root as if we have max path in either left or right subtree
  maxSum[0] = Math.max(maxSum[0], leftSum+rightSum+node.key);
  
  //return max in this current path that starts or ends at current root and doesn't go through it
  return Math.max(leftSum, rightSum) + node.key;
 }

Max depth or Height of Binary Tree
This is same as the number of nodes in the longest path. We can see that longest path with just one node is 1 i.e. the node itself. So, height aka max depth aka longest path is one more than the max of left or right sub tree height.
height(T) = max{height(T.left), height(T.right)}+1;
public static int maxDepth(BTNode root) {
     
     if(root == null){
         return 0;
     }
     
     int leftDepth = maxDepth(root.left);
     int rightDepth = maxDepth(root.right);
     
     return Math.max(leftDepth, rightDepth)+1;     
 }

Find distance between given two nodes
Distance between two nodes is the minimum number of edges to be traversed to reach one node from other. Note that, any two node in the tree must have a common ancestor. So, we can compute Lowest Common Ancestor (LCA) for the given two nodes and then we can find distance between two nodes as follows –
lca = LCA(root, a, b);
d(a, b) = d(root, a)+d(root, b)-2*d(root, lca) , which is equivalent to
d(a,b) = level(a)+level(b)-2*level(lca).
So, basically we need two helper function to compute LCA and Level of the nodes. Below is an O(n) time algorithm
 public static int getLevel(BTNode root, int count, BTNode node){
  if(root == null){
   return 0;
  }
  
  if(root == node){
   return count;
  }
  
  int leftLevel = getLevel(root.left, count+1, node);
  if(leftLevel != 0){
   return leftLevel;
  }
  int rightLevel = getLevel(root.right, count+1, node);
  return rightLevel;
 }
 
 public static BTNode LCA(BTNode root, BTNode x, BTNode y) {
   if (root == null) return null;
   if (root == x || root == y) return root;

   BTNode leftSubTree = LCA(root.left, x, y);
   BTNode rightSubTree = LCA(root.right, x, y);

   //x is in one subtree and and y is on other subtree of root
   if (leftSubTree != null && rightSubTree != null) return root;  
   //either x or y is present in one of the subtrees of root or none present in either side of the root
   return leftSubTree!=null ? leftSubTree : rightSubTree;  
}
 
 public static int shortestDistance(BTNode root, BTNode a, BTNode b){
  if(root == null){
   return 0;
  }
  
  BTNode lca = LCA(root, a, b);
  //d(a,b) = d(root,a) + d(root, b) - 2*d(root, lca)
  return getLevel(root, 1, a)+getLevel(root, 1, b)-2*getLevel(root, 1, lca);
 }

Diameter of Binary Tree
The diameter of a tree is the number of nodes on the longest path between any two leaves in the tree.
The diameter of a tree T is the largest of the following quantities:
* the diameter of T’s left subtree
* the diameter of T’s right subtree
* the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)
D(T) = max{ D(T.left), D(T.right), LongestPath(T.root)}
LongestPath(T.root) = 1+height(T.root..left)+height(T.root.right)
height(T) = 1+max{height(T.left) , height(T.right) }
public static int diameter(BTNode root){
 //D(T) = max{D(T.left), D(T.right), LongestPathThrough(T.root)}
 if(root == null){
  return 0;
 }
 
 int leftHeight = maxDepth(root.left);
 int rightHeight = maxDepth(root.right);
 
 int leftDiameter = diameter(root.left);
 int rightDiameter = diameter(root.right);
 
 return Math.max(Math.max(leftDiameter, rightDiameter), leftHeight+rightHeight+1);
}

However, we can save some height computation overhead by computing the height while traversing the tree down from root. Below is a O(n) implementation of diameter.
public static int diameter(BTNode root, int[] height){
 if(root == null){
  height[0] = 0;
  return 0;
 }
 
 int[] leftHeight = {0}, rightHeight = {0};
 int leftDiam = diameter(root.left, leftHeight);
 int rightDiam = diameter(root.right, rightHeight);
 
 height[0] = Math.max(leftHeight[0],rightHeight[0])+1;
 
 return Math.max(Math.max(leftDiam, rightDiam), leftHeight[0]+rightHeight[0]+1);
}

Mirror Tree
swap left and right subtree recursively in tail recursion manner.
public static void mirrorTree(BTNode root){
 if(root == null){
  return;
 }
 
 mirrorTree(root.left);
 mirrorTree(root.right);
 
 BTNode temp = root.right;
 root.right = root.left;
 root.left = temp;
}

Closest Leaf
Idea is pretty straightforward traverse left sub tree in DFS to find closest leaf. Then we backtrack to to root and traverse ins right subtree for closest leaf. Once both subtree are done we return minimum path length. Whenever we reach a leaf node we update a global max based on returned closest path length of left and right subtree. We also keep track of the closest leaf.
public static BTNode closestLeaf(BTNode root, int[] len, BTNode closest){
 if(root == null){
  return closest;
 }
 
 len[0]++;
 closest = closestLeaf(root.left, len, closest);
 if(root.left == null && root.right == null){
  if(len[0] < len[1]){
   len[1] = len[0];
   closest = root;
  }
 }
 len[0]--;
 closest = closestLeaf(root.right, len, closest);
 
 return closest;
}






No comments:

Post a Comment

Labels

GeeksforGeeks (976) Algorithm (811) LeetCode (654) to-do (599) Review (362) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (263) Google Interview (233) LeetCode - Review (233) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) Binary Tree (58) List (58) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Jobdu (39) Interval (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Space Optimization (34) Array (33) Trie (33) prismoskills (33) Backtracking (32) Segment Tree (32) Union-Find (32) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) DFS + Review (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Bisection Method (14) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Divide and Conquer (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) Suffix Tree (8) System Design (8) Tech-Queries (8) Time Complexity (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Kadane’s Algorithm (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parent-Only Tree (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts