Binary Tree Postorder Traverse - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series

---

Post Order Traverse

• what we need to return to our caller/parent node
  
• when handle parent node, children are already handled
  
• related with divide and conquer, merge sort
  
• preorder traverse can be faster than post order; as it can exit early

Path may not pass through the root

• return value for single path
  
• maintain max value across the node
  
• LeetCode 687 - Longest Univalue Path
  • local + global max
    
  • return local max: Longest Univalue Path for single path
• Find the maximum path sum between two leaves of a binary tree

Binary Tree Reverse Traversal

• LeetCode 971 - Flip Binary Tree To Match Preorder Traversal
  • return passed index

  public boolean dfs(TreeNode node, int[] v) {
    if (node == null) return true;
    if (node.val != v[i++]) return false;
    if (node.left != null && node.left.val != v[i]) {
        res.add(node.val);
        return dfs(node.right, v) && dfs(node.left, v);
    }
    return dfs(node.left, v) && dfs(node.right, v);
  }

Simple

• LeetCode 814 - Binary Tree Pruning
  • alternative
• LeetCode 663 - Equal Tree Partition
  
• LeetCode 366 - Find Leaves of Binary Tree
  
• Check if a given Binary Tree is SumTree
  
• LeetCode 333 - Largest BST Subtree
  
• Print ancestors of a given binary tree node
  
• LeetCode 298 - Binary Tree Longest Consecutive Sequence: from parent to child
  
• LeetCode 549 - Binary Tree Longest Consecutive Sequence II: include child-Parent-child order
  • Result:{inc, dec, node}
• LeetCode 652 - Find Duplicate Subtrees
  • Use unique identifier to reduce time complexity
    
  • long key = ((long)root.val) << 32 | getId(root.left) << 16 | getId(root.right);

  Map<String, Integer> count;
  List<TreeNode> ans;
  public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    count = new HashMap();
    ans = new ArrayList();
    collect(root);
    return ans;
  }
  public String collect(TreeNode node) {
    if (node == null) return "#";
    String serial = node.val + "," + collect(node.left) + "," + collect(node.right);
    count.put(serial, count.getOrDefault(serial, 0) + 1);
    if (count.get(serial) == 2)
        ans.add(node);
    return serial;
  }

• LeetCode 979 - Distribute Coins in Binary Tree

public int dfs(TreeNode node) {
  if (node == null)
    return 0;
  int L = dfs(node.left);
  int R = dfs(node.right);
  ans += Math.abs(L) + Math.abs(R);
  return node.val + L + R - 1;
}

• LeetCode 236 - Lowest Common Ancestor in a Binary Tree

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q)
        return root;
    TreeNode leftN = lowestCommonAncestor(root.left, p, q);
    TreeNode rightN = lowestCommonAncestor(root.right, p, q);
    if (leftN != null && rightN != null)
        return root;// case:left is p/q and right is q/p root is LCA
    if (leftN == null)
        return rightN;// case: p,q both in right subtree, right is LCA
    return leftN;// case: both in left, left is LCA
}

• LeetCode 114 - Flatten Binary Tree to Linked List: pre-order
  • post-order
    
  • save all nodes into a list then link them

  // post-order, return tail
  TreeNode flatten(TreeNode root) {
  if (root == null)
    return null;
  
  TreeNode leftTail = flatten(root.left);
  TreeNode rightTail = flatten(root.right);
  
  if (root.left != null) {
    TreeNode temp = root.right;
    root.right = root.left;
    root.left = null;
    leftTail.right = temp;
  }
  if (rightTail != null)
    return rightTail;
  if (leftTail != null)
    return leftTail;
  return root;
  }

• LeetCode 236 - Lowest Common Ancestor of a Binary Tree

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
   if (!root || p == root || q == root) return root;
   TreeNode left = lowestCommonAncestor(root->left, p, q);
   if (left!=null && left != p && left != q) return left; // optimize
   TreeNode right = lowestCommonAncestor(root->right, p , q);
　　　　if (left && right) return root;
   return left ? left : right;
}

• LeetCode 543 - Diameter of a Binary Tree
  • General tree
    
  • child-parent-child

  int ans;
  public int diameterOfBinaryTree(TreeNode root) {
    ans = 1;
    depth(root);
    return ans - 1;
  }
  public int depth(TreeNode node) {
    if (node == null) return 0;
    int L = depth(node.left);
    int R = depth(node.right);
    ans = Math.max(ans, L+R+1);
    return Math.max(L, R) + 1;
  }
  // General tree
  public int findDiameter(TreeNode root) {
    if (root == null) return 0;
    helper(root);
    return diameter;
  }
  int diameter = Integer.MIN_VALUE;
  private int helper(TreeNode root) {
    int a = Integer.MIN_VALUE;
    int b = Integer.MIN_VALUE;
    for (TreeNode child : root.children) {
        if (child == null) continue;
        int tmp = helper(child);
        if (tmp > a) { b = a; a = tmp;}
        else if (tmp > b) b = tmp;
    }
  
    if (b >= 0) diameter = Math.max(diameter, a + b + 2);
    if (a >= 0) {
        diameter = Math.max(diameter, a + 1);
        return a + 1;
    }
    return 0;
  }

• LeetCode 110 - Balanced Binary Tree
  • ResultType: {isBalanced, maxDepth}
    
  • not necessary better

  public boolean isBalanced(TreeNode root) {
    return maxDepth(root) != -1;
  }
  private int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    if (left == -1 || right == -1 || Math.abs(left-right) > 1) {
        return -1;
    }
    return Math.max(left, right) + 1;
  }

• LeetCode 124 - Binary Tree Maximum Path Sum

public int maxPathSum(TreeNode root) {
    int[] max = new int[1];
    max[0] = Integer.MIN_VALUE;
    maxPathSum(max, root);
    return max[0];
}
private int maxPathSum(int[] max, TreeNode root){
    if(root == null)
        return 0;
    int leftMax =  Math.max(0, maxPathSum(max, root.left));
    int rightMax = Math.max(0, maxPathSum(max, root.right));
    max[0] = Math.max(max[0],  root.val+leftMax+rightMax);
    return root.val+Math.max(leftMax,rightMax);
}

• LintCode 628 - Maximum Subtree
  
• LintCode 597 - Subtree with Maximum Average: ResultType{sum, size}

private class ResultType {
    public int sum, size;
    public ResultType(int sum, int size) {
        this.sum = sum;
        this.size = size;
    }
}
private TreeNode subtree = null;
private ResultType subtreeResult = null;
public TreeNode findSubtree2(TreeNode root) {
    helper(root);
    return subtree;
}
private ResultType helper(TreeNode root) {
    if (root == null) {
        return new ResultType(0, 0);
    }

    ResultType left = helper(root.left);
    ResultType right = helper(root.right);
    ResultType result = new ResultType(
        left.sum + right.sum + root.val,
        left.size + right.size + 1
    );

    if (subtree == null ||
        subtreeResult.sum * result.size < result.sum * subtreeResult.size
    ) {
        subtree = root;
        subtreeResult = result;
    }
    return result;
}