limitPathSum

Write a method limitPathSum that removes nodes to guarantee that the sum of the values on any path from the root to a node does not exceed some maximum value.

Suppose a tree stores the values in following pic:

Calling tree.limitPathSum(50) will remove the node with 12 because the sum of the values from the root to that node is greater than 50 (29 + 17 + -7 + 12 = 51).

Similarly, we have to remove the node with 37 because its sum is too high (29 + 17 + 37 = 83). Removing the node with 37 removes the entire subtree including the node with 16.

We also remove the subtree rooted at value 14 because its sum is high enough (29 + 15 + 14 = 58).

Thus we produce the following tree:

The codes provided are following:

// An IntTree represents a binary tree of integers public class IntTree { private IntTreeNode overallRoot;

public void limitPathSum(int max) { // TODO: Your code here }

public static void main(String[] args) { IntTree tree = new IntTree("[29 [17 [-7 [11] [12]] [37 null [16]]] [15 [4] [14 [-9] [19]]]]"); tree.limitPathSum(50); System.out.println(tree); }

//////////////////////////////////////////////////

// Constructs a tree with default numbers public IntTree() { overallRoot = null; }

// Constructs a tree from the given text representation public IntTree(String s) { overallRoot = fromString(s); }

// post: Prints the numbers in this tree in a pre-order fashion. public void print() { print(overallRoot); }

private void print(IntTreeNode root) { if (root != null) { System.out.print(root.data + " "); print(root.left); print(root.right); } }

// post: Returns true if o is an IntTree with the same values public boolean equals(Object o) { if (this == o) { return true; } else if (!(o instanceof IntTree)) { return false; } else { IntTree other = (IntTree) o; return toString().equals(other.toString()); } }

// post: Returns a text representation of the tree public String toString() { return toString(overallRoot); }

private String toString(IntTreeNode root) { if (root == null) { return "null"; } else if (root.left == null && root.right == null) { return "[" + root.data + "]"; } else { return "[" + root.data + " " + toString(root.left) + " " + toString(root.right) + "]"; } }

// An IntTreeNode represents a single node in a binary tree private static class IntTreeNode { public int data; public IntTreeNode left; public IntTreeNode right;

// post: Constructs a leaf node with given data public IntTreeNode(int data) { this(data, null, null); }

// post: Constructs a leaf or branch node with given data and links public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) { this.data = data; this.left = left; this.right = right; } }

private static IntTreeNode fromString(String s) { s = s.trim(); if (s.isEmpty() || s.equals("null")) { return null; } s = s.substring(1, s.length() - 1); try { return new IntTreeNode(Integer.parseInt(s.trim())); } catch (NumberFormatException e) { String[] pair = s.trim().split(" +", 2); int data = Integer.parseInt(pair[0]); int index = splitIndex(pair[1]); String left = pair[1].substring(0, index); String right = pair[1].substring(index); return new IntTreeNode(data, fromString(left), fromString(right)); } }

private static int splitIndex(String s) { if (s.startsWith("null")) { return 4; } int brackets = 0; for (int i = 0; i +----+ | 29 | +- + | / | +-- - + +----+ | 17 | | 15 | +- + +----+ | | | | +----+ +----+ +----+ +----+ | -7 | | 37 | | 4 | 14 | + + +----+ +-- + +- - + 1 | +----+ +- + +----+ +-- + +-- + | 11 | | 12 | | 16 | | -9 | | 19 | +----+ +----+ +----+ +----+ +-- - + +----+ | 29 | +----+ | +- + +----+ | | 17 | | 15 | +----+ +----+ / +----+ +----+ | -7 | | 4 | +----+ +----+ / +----+ | 11 | +----+