Binary tree deepcopy using the Morris traversal in C

Question

I need to perform a deep copy of a binary tree using the Morris traversal.

I think I managed to do it, that is the code below returns what I expect; however, I am not 100% sure I have covered every corner case.

I would appreciate it if someone could confirm my implementation:

• Doesn't create new nodes on top of existing nodes (i.e. leak memory)
• Won't break under some corner case tree structure (i.e. the tree has 5 left nodes in a row with no right ones or something like that).

Also, if any optimisations are possible, please let me know.

Example code:

#include <stdio.h>
#include <stdlib.h>
typedef struct tNode
{
 int data;
 struct tNode* left;
 struct tNode* right;
}tNode;
tNode* newtNode(int data)
{
 tNode* node = (tNode *)malloc(sizeof(tNode));
 node->data = data;
 node->left = NULL;
 node->right = NULL;
 return node;
}
void MorrisTraversalCopy(tNode* original, tNode** clone)
{
 tNode *current = original;
 tNode *cloneCurrent = newtNode(0);
 tNode *pre = NULL;
 tNode *clonePre = NULL;
 *clone = cloneCurrent;
 /* Inorder Morris traversal */
 while (current != NULL)
 {
 if (current->left == NULL)
 {
 cloneCurrent->data = current->data;
 current = current->right;
 cloneCurrent = cloneCurrent->right;
 }
 else
 {
 /* Esure the left node is not created again when we climb back */
 if(!cloneCurrent->left)
 {
 cloneCurrent->left = newtNode(0);
 }
 /* Find the inorder predecessor of current */
 pre = current->left;
 clonePre = cloneCurrent->left;
 while (pre->right != NULL
 && pre->right != current)
 {
 /* Create a new right node if:
 * - The pre->right has real node, not one used for climbing back
 * - Only if this iteration will terminate due to
 * pre->right == NULL (i.e. this is the first time the
 * iteration is done) */
 if(!clonePre->right && pre->right && pre->right != current)
 {
 clonePre->right = newtNode(0);
 }
 clonePre = clonePre->right;
 pre = pre->right;
 }
 /* Make current as the right child of its
 inorder predecessor */
 if (pre->right == NULL)
 {
 clonePre->right = cloneCurrent;
 cloneCurrent = cloneCurrent->left;
 pre->right = current;
 current = current->left;
 }
 /* Revert the changes made in the 'if' part to
 restore the original tree i.e., fix the right
 child of predecessor */
 else
 {
 cloneCurrent->data = current->data;
 /* Create a new node if it wasn't created in the while loop
 * I believe this happens only on the first iteration that starts
 * exploring the right subtree of the root (original) node */
 if (!cloneCurrent->right)
 {
 cloneCurrent->right = newtNode(0);
 }
 clonePre->right = NULL;
 cloneCurrent = cloneCurrent->right;
 pre->right = NULL;
 current = current->right;
 }
 }
 }
}
void debugPrintTree(tNode *root)
{
 if(root->left)
 {
 debugPrintTree(root->left);
 }
 printf("%d ", root->data);
 if(root->right)
 {
 debugPrintTree(root->right);
 }
}
int main()
{
 /* Constructed binary tree is
 1
 / \
 2 3
 / \
 4 5
 / \
 6 7
 \
 8
 */
 tNode* root = newtNode(1);
 root->left = newtNode(2);
 root->right = newtNode(3);
 root->left->left = newtNode(4);
 root->left->right = newtNode(5);
 root->left->left->left = newtNode(6);
 root->left->right->right = newtNode(7);
 root->left->left->left->right = newtNode(8);
 tNode *clone;
 MorrisTraversalCopy(root, &clone);
 printf("root = ");
 debugPrintTree(root);
 printf("\nclone= ");
 debugPrintTree(clone);
 return 0;
}

Please focus on the Morris Traversal function. Everything else I hacked together in a few minutes to create this post.

Also I realised I do not check for memory allocation failures and recovering from that will be tricky since the traversal modifies both trees, creating temporary loops. I am open to ideas on how to overcome this and cleanup.

• ad absurdum: tNode* node = (tNode *)malloc(sizeof(tNode)); --> tNode* node = malloc(sizeof *node);. I realize that you are only interested in commentary about MorrisTraversalCopy, but you should be open to commentary about other code. This malloc call is un-idiomatic in C. Better to avoid casting the result of malloc, and using the expression *node instead of the type tNode is easier to maintain.
• U. Windl: I saw macros like #define NEW(x) (x *) malloc(sizeof(x)). Doesn't look very wrong IMHO.
• ad absurdum: @U.Windl -- "I saw macros like...." Yes, people write terrible macros all the time.
• U. Windl: Maybe, but at least you cannot easily assign a a NEW(dog) to a cat ;-)

Answer 1

single responsibility

I need to perform a deep copy of a binary tree using the Morris traversal.

Ok, maybe you. I confess it's not obvious to me why that is.

Consider making the underlying binary tree code responsible for creating an ordinary deepcopy. And then caller passes you such a copy, which you can mangle and thread to your heart's content. Or consider offering a deepcopy utility function, separate from the Morris threading.

naming

tNode* newtNode(int data)

I don't get it.

I mean, newts are beautiful, nothing against them. newt

But surely we wanted newTNode here, no?

If single-letter troubles you, perhaps newTmpNode would be better, or newTrNode if "traversal" was your intent.

Using new or copy in the name seems awkward and inconvenient. This brings us back to the topic of separating deepcopy from traversal.

nit, typo: Esure

test suite

An automated unit test "knows the right answer" so it can display a Green bar when run. Exercising the target code via the main() function is helpful, and I thank you for it. But a test where I don't need to eyeball the results would be an improvement.

serialization

Which brings us to the topic of concise representations of a datastructure, suitable for comparisons within a unit test. You might choose to define a JSON format for the tree types of interest, and then exploit that within your test suite.

• Slav: Thanks for responding, but this is in C, not C++. Also regarding the code - as I said in the OP - this is an example code I hacked together to make this post. I only care about the Morris traversal function.
• J_H: I stand corrected: underlying binary tree <s>class</s> code

Answer 2

tNode* node = (tNode *)malloc(sizeof(tNode));

In ancient times, malloc() used to return a char *, which had to be cast to the proper type. Since C89, or around 35 years, malloc() returns a generic void * that is implicitly converted to and from any other pointer type.

So the cast can, and should be, elided.

tnode *node = malloc(sizeof *node);

Note that I used the size of the object instead of the referenced type. In the case that tnode was changed to some other type, we'd not need to make any change to the malloc() call.

Furthermore, malloc() and family returns a null pointer on failure. Failing to check for it risks invoking undefined behavior.

So the final code becomes:

tNode *node = malloc(sizeof *node);
if (node == NULL) {
 // Handle error here, perhaps by returning NULL.
}

If instead you were to use calloc() here, you wouldn't need to set the left and right pointers to NULL.

I also do not see any calls to free() in your code. You're leaking all the allocated memory.

• Slav: As I said in the OP - this is an example code I hacked together to make this post. I only care about the Morris traversal function. Everything else you see will not be present in the final implementation. Regarding malloc - in the real implementation this will be replaced by a call to a function for the specific port, which must somehow allocate memory to me, so I have no control over it. But good point about the malloc failure - recorevering from it will b e tricky though since the Morris traversal modifies the leaf trees, creating temporary loops. How I overcome this and clean up?
• J_H: You’re saying that doing Two Things is "hard". I completely agree. Better to do a Single Thing well. It’s easier to design, easier to test. Recommend you get around to writing a simple deepcopy() for binary tree, and then the whole business of "yikes, I trashed caller’s only copy of tree!" magically disappears. // As far as malloc fail goes, just be honest with the caller. Immediately return NULL and confess that the traversal tree is toast. Alternatively, do all allocations during first traversal, then on second traversal make mutations.