Ankit Sinha
BAN USERCan be done in n log n if tree is balanced.
Algo:
1. Conduct a depth first traversal
2. At each stage, maintain a list of ancestors (size log n if balanced)
3. For each ancestor, add to sum if condition is met
4. Add self to list of ancestors and traverse children
5. Get the sum calculated during the traversal of the children
import java.util.List;
public class TreeValueAdjuster {
public static interface TreeNode {
public TreeNode getLeft();
public TreeNode getRight();
public int getValue();
public TreeNode setValue(int value);
}
public static interface NodeVisitor {
public void visit (TreeNode node);
public void afterAllVisited();
}
public static class SumVisitor implements NodeVisitor {
public void visit (TreeNode visitedNode) {
if (meetsCondition(visitedNode)) {
operate(visitedNode);
}
}
public SumVisitor(TreeNode node) {
this.startingNode = node;
}
private boolean meetsCondition (TreeNode visitedNode) {
return visitedNode.getValue() < startingNode.getValue();
}
private void operate (TreeNode visitedNode) {
sum += visitedNode.getValue();
}
public void afterAllVisited() {
startingNode.setValue(sum);
}
private final TreeNode startingNode;
private int sum = 0;
}
public static interface VisitorFactory {
public NodeVisitor createVisitor (TreeNode node);
}
public static class SumVisitorFactory implements VisitorFactory {
public NodeVisitor createVisitor (TreeNode node) {
return new SumVisitor(node);
}
}
public List<NodeVisitor> traverseTree (TreeNode node, List<NodeVisitor> visitors, VisitorFactory factory) {
for (NodeVisitor visitor: visitors) {
visitor.visit(node);
}
NodeVisitor visitor = factory.createVisitor(node);
visitors.add(visitor);
if (node.getLeft() != null) {
traverseTree(node.getLeft(), visitors, factory);
}
if (node.getRight() != null) {
traverseTree(node.getRight(), visitors, factory);
}
visitors.remove(visitors.size());
visitor.afterAllVisited();
return visitors;
}
}
To get the same BST, a number should be listed only after its parent.
This is identical to traversing through the BST. So the permutations can be arrived at by performing all possible traversals of the tree.
//Traverse the tree in all possible permutations
//Take a node from the boundary and
// append it to the traversal.
// Remove the node from the boundary and
// add its children. Recurse with the new boundary.
//Iterate with all nodes in the bounbdary,
// concatenate and return the results
//Initially, the traversal will be empty,
// and the boundary will be the root
tp.traverseall = function (boundary, traversal) {
var results = [], i, permutation, node;
traversal = traversal || [];
if(boundary.length === 0) {
//Entire tree has been traversed
//Return the input traversal itself as the only result
return [traversal]
}
for (i=0; i< boundary.length; i++) {
permutation = {
boundary:null,
traversal:null,
results:null
};
//Remove the ith node
permutation.boundary = boundary.slice();
permutation.boundary.splice(i, 1);
node = boundary[i];
//Add its children
if(node.left) {
permutation.boundary.push(node.left);
}
if(node.right) {
permutation.boundary.push(node.right);
}
//Fork a new traversal from the input traversal and
//append the current node to it.
permutation.traversal = traversal.slice();
permutation.traversal.push(node.data)
//Recursse
permutation.results = tp.traverseall(permutation.boundary, permutation.traversal);
//Concatenate results from all iterations
results = results.concat(permutation.results);
}
return results;
}
If it is simple, the explanation could have been shorter ;)
And it could focus more on g(Y,Z) as it seems to be half the code size
At every node, will it be required to iterate over the entries in the map and add to sum if the condition is met? If so, time complexity will be be n * log n
- Ankit Sinha February 16, 2015