CareerCup

cslibrary.stanford.edu/110/BinaryTrees.html

I guess its enough to do and inorder or perorder or post order traversal

1. Create an array of size d, say 'path'.

2. Maintain an int variable, say `pos` initialized to 0 which will track the current node you're at in a path.

3. Begin pre-order traversal with arguments as root of the tree, `pos` = 0 and `path`

4. Do pre-order traversal, at each node:
a. If node is leaf node (no left or right children), print path as all values in `path` from 0 to `pos` and return
a. Else, place the node's value into the array `path` at index `pos`
b. Call pre-order traversal for (node.left, path, pos+1)
c. Call pre-order traversal for (node.right, path, pos+1)

I would use level-order tree traversal:

void printAllPathsFromRoot(){
		
		Queue<PathEntry> queue = new LinkedList<PathEntry>();		
		
		queue.add( new PathEntry((BSTEntity)root, (String)root.getValue()) );
		
		while( ! queue.isEmpty() ){		
			PathEntry pathEntry = queue.poll();
			
			if( pathEntry.entry.isLeaf() ){
				System.out.println( pathEntry.path );
			}
			
			if( pathEntry.entry.hasLeft() ){
				queue.add( new PathEntry((BSTEntity)pathEntry.entry.getLeft(), pathEntry.path + "/" + (String)pathEntry.entry.getLeft().getValue() ) );
			}
			
			if( pathEntry.entry.hasRight() ){
				queue.add( new PathEntry((BSTEntity)pathEntry.entry.getRight(), pathEntry.path + "/" + (String)pathEntry.entry.getRight().getValue() ) );
			}
		}
	}
	
	static class PathEntry {		
		
		PathEntry(BSTEntity entry, String path) {
			super();
			this.entry = entry;
			this.path = path;
		}
		
		BSTEntity entry;
		String path;		
	}

Would print something like this:

3/1/2
3/6/4
3/6/7/8

rootToLeaf(nodeptr root)
{
    int path[1000];
    rootToLeafPath(root,path,0);
}
rootToLeafPath(nodept root,int path[],int pathlen)
{
   if(!root) return;
   path[pathlen++]=root->data;
   if(!root->left && !root->right)  //leaf
   {
         printarray(path,pathlen);
         return;
   }
   else
   {
         rootToLeafPath(root->left,path,pathlen);
         rootToLeafPath(root->right,path,pathlen);
         }
}
printarray(int path[],int pathlen)
{
    for(int i=0;i<=pathlen;i++)
        cout<<root->data;
}

if it is a 'Binary Tree' then wont there be a single path from root to the node? why say all paths?

Hi Myth,
All paths mean "each path to the each leaf Node".
Following is my code:

package com.test;

public class BSTPaths {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node root = new Node(5);
		Node a = new Node(3);
		Node b = new Node(4);
		root.setLeft(a);
		a.setRight(b);
		
		Node c = new Node(7);
		Node d = new Node(8);
		Node e = new Node(6);
		c.setRight(d);
		c.setLeft(e);
		root.setRight(c);
		
		traverse(root, new int[]{});
	}

	private static void traverse(Node root, int []prev) {
		if(root == null) {
			return;
		}
		int arr[] = new int[prev.length + 1];
		for(int i = 0; i < prev.length; i++) {
			arr[i] = prev[i];
		}
		arr[arr.length - 1] = root.getData();
		if(root.getLeft() == null && root.getRight() == null) {
			printPath(arr);
		} else {
			traverse(root.getLeft(), arr);
			traverse(root.getRight(), arr);
		}
	}
	
	private static void printPath(int[] arr) {
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]);
			if(arr.length - 1== i) {
				System.out.println();
			} else {
				System.out.print(", ");
			}
		}
	}

	private static class Node {
		public Node() {
			// TODO Auto-generated constructor stub
		}
		public Node(int data) {
			this.data = data;
		}
		private Node left;
		private Node right;
		private int data;

		public Node getLeft() {
			return left;
		}
		public void setLeft(Node left) {
			this.left = left;
		}
		public Node getRight() {
			return right;
		}
		public void setRight(Node right) {
			this.right = right;
		}
		public int getData() {
			return data;
		}
		public void setData(int data) {
			this.data = data;
		}
	}
}