Thursday, November 17, 2011

Printing paths from root to all leaf nodes


/**
 Given a binary tree, prints out all of its root-to-leaf
 paths, one per line. Uses a recursive helper to do the work.
*/
public void printPaths() {
  int[] path = new int[1000];
  printPaths(root, path, 0);
}
/**
 Recursive printPaths helper -- given a node, and an array containing
 the path from the root node up to but not including this node,
 prints out all the root-leaf paths.
*/
private void printPaths(Node node, int[] path, int pathLen) {
  if (node==null) return;

  // append this node to the path array
  path[pathLen] = node.data;
  pathLen++;

  // it's a leaf, so print the path that led to here
  if (node.left==null && node.right==null) {
    printArray(path, pathLen);
  }
  else {
  // otherwise try both subtrees
    printPaths(node.left, path, pathLen);
    printPaths(node.right, path, pathLen);
  }
}

/**
 Utility that prints ints from an array on one line.
*/
private void printArray(int[] ints, int len) {
  int i;
  for (i=0; i<len; i++) {
   System.out.print(ints[i] + " ");
  }
  System.out.println();
}

No comments:

Post a Comment