Linear Tree Traversal

Linear Tree Traversals
This is useful if you want to simulate going through a tree in sorted order, as if the tree was a linear list, and the list was sorted.
There are two mechanisms how this is done, one called "linking," which we will not discuss, and the other is going and finding the lowest element in the tree, and traversing it in such a way, where we go from least to highest. The latter is the one which I will discuss.

So, there are two pieces to this linear traversal.
First, to find the lowest element, this is just a matter of going left, until you can't.
Second, to find the next element, you can do one of two things. You want to go right, and then all the way down to the left most node. If you have no right child node, then you are left to go up. There are two cases, one where you are the left or the right child of your parent.

If you are a left child of your parent, it hasn't been "traversed," therefore pick that element. Else if you are the right child of your parent, the parent node has been "traversed" so keep going up until you are not the right child of your parent.

Before, displaying the code, let's prove that going up (once, if you are the left, and continuously, until you hit NULL, if you are continuously the right) will indeed be the right choise.

Ok, starting off you are the left most node in the tree. This guarantees that you are the "lowest" node in the tree. However, if you look at its parent node, it is still bigger then the "lowest" node's right node. So, instead of going up, you'd want to go right, and then follow its left chain all the way down.
However, if you are a right child, then to even get to that point your parent node has been traversed. Why? This is because to get to the right node, you have had to traverse the parent, to even get to the right node. This is in part due to the fact that, we go right, then all the way down left. And once we bubble up to that "subroot" which is the right child, we "traverse" it, and then go to its right node, and then to the lowest node in that subtree. So, in doing so, when we bubble back up, there is no need to look at the parent node of the right child.

The code follows:

typedef struct node {
   struct node * left;
   struct node * right;
   struct node * parent;
   int val;
} uwf_node_t;

// Find the first node in the tree.
uwf_node_t * findFirst(uwf_node_t * root) {
   if (!root) {
      return (uwf_node_t *)NULL;
   }
   while (root->left)
      root = root->left;
   // Return the left most node.
   return (root);
}
uwf_node_t * findNext(uwf_node_t * subRoot) {
   if (!subRoot) 
      return (uwf_node_t *)NULL;
   // Let's suppose, we are the left most node
   // instead of bubbling up, we need to go right,
   // and then left as far as possible.
   if (subRoot->right) {
      subRoot = subRoot->right;
      while (subRoot->left)
         subRoot = subRoot->left;
   } else {
      uwf_node_t * oldRoot = subRoot;
      // Find the parent node that is "valid"
      while (subRoot = subRoot->parent) {
         if (subRoot->left == oldRoot)
            break;
         oldRoot = subRoot;
      }
   }
   return (subRoot);
}