CareerCup

For binary tree:

preorder traversal:
{
   if( i'm null ) return;
   
   add "me.data" to end of a vector/arrayList;

   if( my chilren are both null ) print out the vector/arrayList;

   recurse into left child;
   recurse into right child;

   delete last element of the vector/arrayList (e.g. removing me.data);
}

For graph do DFS with a check for visited flags (do the check before extending path there) using same idea above.

NOTE: preorder(tree) == DFS(graph) - (need for visited flags)

Who interviewed you? Why does it say "Later..." ?

I've seen this on a programming challenge website.

Same as Sound Wave's solution.
Here's the pseudo code.

void printGraph(Node *root) {
   static DeQueue<int> q;   // this is store a path. DeQueue to access from front and back.
   static set<Node*> visited;
   if (NULL == root) { 
     // this will print the contents of q from head to tail. this is a full path.
     printDeQueue(q); 
     return;
   }
   visisted.insert(root); // mark node as visited.
   q.push(root->data);
   Node *c;
   for_each(c in root->children){
   	  if(visited.find(c) != visited.end()) { //already visited. cycle.
   	  	printDeQueue(q); // print the path
   	  	continue;
   	  }
   	  q.push_back(c);
   	  printGraph(c);
   	  q.pop_back();
   }
}

#include "stdafx.h"
#include "iostream"
#include "string"
#include "stack"
using namespace std;
class Node {
public:
	Node * left_child;
	Node * right_child;
	Node(){
		left_child = NULL;
		right_child = NULL;
	}
	bool is_leaf(){
		return !left_child && ! right_child;
	}

};
struct Tree {
	
	stack <string> path;
	Node * head;
	void print_node (Node * node, string ss) {
		if(node == NULL) {
			return;
		} else if(node->is_leaf()){
			path.push(ss.append("/"));
			cout<<ss<<endl;
		} else {
			string buffer1 = ss;
		
			buffer1.append("/leftchild");
	
			string buffer2 = ss;
			buffer2.append("/rightchild");
			print_node(node->left_child, buffer1);
		
			print_node(node->right_child, buffer2);
			
		}
	}
	void print_path(void){
		print_node(head, "");
	}
};

int main(int argc, _TCHAR* argv[])
{
	Tree tree;
	Node head;
	Node left;
	Node right;
	Node left_left;
	left.left_child = &left_left;
	head.left_child = &left;
	head.right_child = &right;
	tree.head = &head;
	tree.print_path();
	int i;
	string ss = "this";
	string s2 (ss);
	s2.append("//");
	cout<< ss<<endl;
	cout<<s2<<endl;
	cin >> i;
	return i;
}

PHP version

Part 1: print all paths of a binary tree

// class for Binary Tree Node
class BinaryNode {
	public $value;
	public $left;
	public $right;

	public function __construct($value) {
		$this->value = $value;
		$this->left = null;
		$this->right = null;
	}

	public function isLeaf() {
		return ($this->left === null && $this->right === null);
	}
}

// Class for Binary Tree
class BinaryTree {
	private $_root;

	public function __construct() {
		$this->_root = null;
	}

	public function isEmpty() {
		return $this->_root === null;
	}

	public function insert($value) {
		$node = new BinaryNode($value);

		if ($this->isEmpty()) {
			$this->_root = $node;
		} else {
			$this->_insertNode($node, $this->_root);
		}
	}

	private function _insertNode(BinaryNode $node, &$subTree) {
		if ($subTree === null) {
			$subTree = $node;
		} 
		// right insert
		elseif ($node->value > $subTree->value) {
			$this->_insertNode($node, $subTree->right);
		} 
		// left insert
		elseif ($node->value < $subTree->value) {
			$this->_insertNode($node, $subTree->left);
		}
	}

	public function getRoot() {
		return $this->_root;
	}
}

function printAllTreePaths(BinaryTree $tree) {
	$root = $tree->getRoot();
	$treePath = '';

	recurseNode($root, $treePath);
}

function recurseNode(BinaryNode $node, $treePath) {

	$treePath .= $node->value;
	
	// if we've hit a leaf, print the current path
	if ($node->isLeaf()) {
		echo $treePath . "\n";
		return;
	}

	// check and recurse left node
	if ($node->left !== null) {
		recurseNode($node->left, $treePath . '<L>');
	}

	// check and recurse right node
	if ($node->right !== null) {
		recurseNode($node->right, $treePath . '<R>');
	}
}

// create and fill the tree

$myTree = new BinaryTree();

for ($i = 0; $i < 100; $i++) {
	$myTree->insert(mt_rand(1,10000));
}

// print the tree
printAllTreePaths($myTree);

public static void printPathsBT(Node root){
	if(root == null) return;
	System.out.print(root.data);
	root.marked = true;
	
	if(root.left != null && root.left.marked == false)
		printPaths(root.left);	
	if(root.right != null && root.right.marked == false)
		printPaths(root.right);	
}

public static void printPathsGraph(Node root){
	if(root == null) return;

	System.out.print(root.data);
	root.marked = true;
	
	for(Node neighbor : root.getNeighbors()){
		if(neighbor.marked == false){
			printPaths(neighbor);
		}
	}
}

public IEnumerable<string> PrintAllPaths(TreeNode root)
{
	var list = new List<string>();
	if (root == null)
		return list;

	var path = new List<int>();

	return list;
}

private void PrintAllPaths(TreeNode node, List<int> path, List<string> list)
{
	if (node == null)
		return;

	path.Add(node.Value);
	if (node.Left == null && node.Right == null)
	{
		var sb = new StringBuilder();
		foreach (var item in path)
			sb.Append(item).Append(", ");
		list.Add(sb.ToString());
	}

	PrintAllPaths(node.Left, path, list);
	PrintAllPaths(node.Right, path, list);

	path.RemoveAt(path.Count - 1);
}

For both the problem its gonna be DFS with the slight change of printing the path before calling recursion. I will write the algo for the graph one.

for node in all_nodes:
	DFS(path, node) {
        print path
	if node in path:
		return
	for child in node.children:
		DFS(path+node, child)}

The visited flag logic is insufficient here as we might have to visit a node more than once if its a part of more than 1 path.