Bst Path

max/min path
int maxPath(Node node) {
  if (node == null) return 0;
 
  return 1 + Max(maxPath(node.left), maxPath(node.right));  
}
print all paths
List<Node> path = new ArrayList<Node>();
printPath(root, path, o); 
 
void printPath(Node node, List<Node> path, int level) {
  if (node == null) {
      for (int i = 0; i < len; i++) {
           System.out.print(path.get(i));
      } 
      System.out.println(); 
      return;
  }
 
  if (level < path.size()) {
     path.set(level, node);
  } else {
    path.add(level, node);
  }
 
  printPath(node.left, path, level + 1);
  printPath(node.right, path, level + 1);
}
convert all levels into linked list
void convertToLinkedList(Node root) {
  List<List<Node>> result = new ArrayList<List<Node>>();
  int level = 0;
 
  List<Node> nextLevel = new LinkedList<Node>();
  nextLevel.add(root);
  result.add(level, nextLevel);
 
  boolean done  = false;
  while (!done) {
     List<Node> nextLevel = new LinkedList<Node>();
     List<Node> currentLevel = result.get(level);
 
     for(Node node :  currentLevel) {
        if (node.left) nextLevel.add(node.left);
        if (node.right) nextLevel.add(node.right);
    } 
 
    if (nextLevel.size() > 0) {
      result.add(level + 1, nextLevel);
    } else {
      done  = true;
    }
    level = level + 1;
  }
}
print all path has sum value

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree. it does not have to start at the root.

void listPath(Node node, int target) {
  List<Node> path = new ArrayList<Node>();
  traversePath(node, target, path, 0);
}
 
void traversePath(Node node, int target, List<Node> path, level) {
  if (node == null) return;
 
  path.add(level, node);
 
  int tmp = target;
  for(int i = level; i >= 0;  i--) {
    tmp = tmp - path.get(i).value;
    if (tmp == 0) printPath(path, i, level); 
  }
 
  traversePath(node.left, target, path.clone(), level + 1);
  traversePath(node.right, target, path.clone(), level + 1);
}
Add a New Comment
or Sign in as Wikidot user
(will not be published)
- +
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License