How to print all the paths from the root to a leaf in a tree

Consider the following tree:

   1:             10

   2:            /   \

   3:           25    7

   4:               /   \

   5:              8     2

There are three paths from the root to a leaf, in this tree:
10 -> 25
10 -> 7 -> 8
10 -> 7 -> 2
Some programming questions I found on the net, and are useful to know, are how to print all these paths, given a tree in a structure as below, and another one, how to find if one of these paths has a certain given sum. Both are solved using recursion.
To print all the paths recursively, we need the current node, and a way to know what path reaches till that node. Therefore we could write something like this:

   1:  void printPaths(struct node* node) { 

   2:      struct node* prevPaths[100];

   3:      int pathLen = 0;

   4:      printPaths(node, prevPaths, pathLen);

   5:  }

So we start out with the root node and an empty list (no paths before the root node). Replacing the array prevPaths[100] with something reasonable is left as a challenge to the reader.

   1:  void printPaths(node* head, node** prevPaths, int pathLen) {

   2:      if (head == 0) { //we have reached the end, print the existing path

   3:          cout << "path: ";

   4:          for (int i = 0; i < pathLen; i++)

   5:              cout << prevPaths[i]->data << " ";

   6:          cout << endl;

   7:          return;

   8:      } //otherwise

   9:      prevPaths[pathLen] = head; //add the current node to the path

  10:      pathLen++; //increase the path length

  11:      if (head->left == 0 && head->right == 0) //if it has no children then call the function one more time to print the paths

  12:          printPaths(head->left, prevPaths, pathLen);

  13:      else if (head->left == 0 && head->right != 0) //if it has one child, continue to it

  14:          printPaths(head->right, prevPaths, pathLen);

  15:      else if (head->left != 0 && head->right == 0)

  16:          printPaths(head->left, prevPaths, pathLen);

  17:      else {

  18:          printPaths(head->left, prevPaths, pathLen);//if it has both children, search both

  19:          printPaths(head->right, prevPaths, pathLen);

  20:      }

How about if you would want to find out if a certain path has a give sum? Following the same principle we get:

   1:  int hasPathSum(struct node* node, int sum) { 

   2:      if (node == 0) //we reached a dead end

   3:          if (sum == 0)

   4:              return 1;

   5:          else

   6:              return 0;

   7:      sum -= node->data; //otherwise continue to each child with the remaining sum

   8:      return max(hasPathSum(node->left, sum), hasPathSum(node->right, sum));    

   9:  }

So we go through each path, removing the current value of the node from the existing sum. If at the end, the sum is 0, then the values from that path add up to exactly the inital sum, otherwise not.

How to mirror a binary tree

Easy, but you have to be prepared for anything :) Mirroring means switching the pointers around, inside of the tree, so that the resulting tree looks like it's mirror copy of the original tree. Here's an example.
So the tree:

   1:             10

   2:            /   \

   3:           7     25

   4:         /   \

   5:        2     8

becomes:

   1:             10

   2:            /   \

   3:           25    7

   4:               /   \

   5:              8     2

The solution has to be O(n) because it has to change all the pointers from all the nodes, so it can't be done faster.

   1:  void mirror(struct node* head) {

   2:      if (head == 0)

   3:          return;

   4:      node* temp = head->left;

   5:      head->left = head->right;

   6:      head->right = temp; // switch left child with right child

   7:      mirror(head->left); // then repeat the process with each child

   8:      mirror(head->right);

   9:  }

This can be easily expanded for generic trees with more than two children, the basic idea remains the same.

How to do BFS/BFT and DFS/DFT in a tree

Another one of the classic interview questions is how to do BFT (breadth-first traversal) and DFT (depth-first traversal) in a tree of some kind. For this purpose I'm going to consider a binary tree, just because the algorithm is shorter to write and easier to understand. It can be applied on any kind of tree.
The structure of a tree node should look like this, resembling the node of a linked list:

   1:  struct node {

   2:      int data;

   3:      struct node* left;

   4:      struct node* right;

   5:  };

The recursive solution for DFT is really easy so I'm not going to write it here. For BFT it's a little more complicated, but I want to focus here on the iterative solutions for both, since they also involve two frequently used data structures, a stack and a queue. In the examples below, I use std::queue and std::stack.

For BFT:

   1:  void bfs(node* head) {

   2:      queue<node*> q;

   3:      q.push(head);

   4:      while (!q.empty()) {

   5:          node* n = q.front();

   6:          q.pop();

   7:          cout << n->data << " ";

   8:          if (n->left != 0)

   9:              q.push(n->left);

  10:          if (n->right != 0)

  11:              q.push(n->right);

  12:      }

  13:      cout << endl;

  14:  }

DFT simply exchanges the queue with a stack:

   1:  void dfs(node* head) {

   2:      stack<node*> q;

   3:      q.push(head);

   4:      while (!q.empty()) {

   5:          node* n = q.top();

   6:          q.pop();

   7:          cout << n->data << " ";

   8:          if (n->left != 0)

   9:              q.push(n->left);

  10:          if (n->right != 0)

  11:              q.push(n->right);

  12:      }

  13:      cout << endl;

  14:  }