Amazon Interview Question
Software Engineer / DevelopersTeam: RCX
Country: United States
Interview Type: In-Person
While I am trying to write this code in C# it does not detect node.left, is there anything I had to include? Could you please help me.
Thanks
What if only the root exists? Then your solution will print out "root" twice.
Need to add an extra check to see if you are not already a leaf (no children).
Perhaps the correction is this:
if (node.left != null)
PrintAllPaths(node.left, pathSoFar + ", " node.data);
if (node.right != null)
PrintAllPaths(node.right, pathSoFar + ", " node.data);
if (node.right == null and node.left == null) // this is a leaf, so just print it out
Console.WriteLine(pathSoFar);
Can be done without recursion:
class Nodex
{
public:
bool visited;
int a;
Nodex* parent;
Nodex* left;
Nodex* right;
};
Nodex* NodeHead;
// set NodeHead to the root
void TraverseWitoutRecursion()
{
Nodex* current;
current = NodeHead;
while(1)
{
if(current==NULL) break;
if((current->left != NULL) && (current->visited==false))
current = current->left;
else
if((current->right != NULL) && (current->visited==false))
current = current->right;
else
if(current->visited==false)
{
printf("node value = %d", current->a);
current->visited = true;
}
else
current = current->parent;
}
}
/*Given a binary tree, print out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do the work.*/
void printPaths(struct node* node)
{
int path[1000];
printPathsRecur(node, path, 0);
}
/* Recursive helper function -- given a node, and an array containing
the path from the root node up to but not including this node,
print out all the root-leaf paths.*/
void printPathsRecur(struct 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 */
printPathsRecur(node->left, path, pathLen);
printPathsRecur(node->right, path, pathLen);
}
}
/* UTILITY FUNCTIONS */
/* Utility that prints out an array on a line. */
void printArray(int ints[], int len)
{
int i;
for (i=0; i<len; i++)
{
printf("%d ", ints[i]);
}
printf("\n");
} http://www.geeksforgeeks.org/archives/6719
inspired by inorder traversal written in c++
void find_path(struct node *ptr, std::string& path)
{
if(ptr == NULL)
return;
if(ptr->l == NULL && ptr->r == NULL)
{
printf("path: %s %d\n", path.c_str(), ptr->n);
return;
}
path.append(1, ' ');
char buf[5]={0};
sprintf(buf, "%d", ptr->n);
path.append(buf);
find_path(ptr->l, path);
find_path(ptr->r, path);
sprintf(buf,"%d", ptr->n);
size_t n = path.rfind(buf);
if(n != std::string::npos)
path = path.substr(0, n);
return;
}
void print_paths(node n1)
{
System.out.println("in print_paths");
if(n1==null)
return;
else
{
arr[jj++]=n1.data;
//System.out.println(sum2);
print_paths(n1.left);
print_paths(n1.right);
if(n1.left==null && n1.right==null)
{
for(int i=0;i<jj;i++)
System.out.print(arr[i]);
}
if(n1!=null)
jj--;
}
}
This method below is not giving correct paths. Can someone please tell me the mistake.
public static void paths(Node node, LinkedList<Integer> list) {
if(node == null) return;
list.add(node.data);
if(node.left == null && node.right == null) {
print(list);
}
else {
paths(node.left, list);
paths(node.right, list);
}
}
public static void print(LinkedList<Integer> list) {
System.out.println("Contents of list: " + list);
}
e.g:
7
/
2
/ \
1 5
It prints:
7 2 1
7 2 1 5
- Anonymous January 06, 2012