Binary Tree Morris Traversal

algorithm cheat sheet

Morris traversal does not need to rely on recursion or stacks. Instead, it reorganize the tree into a thread that forms a certain sequence. It does modify the structure of the original tree. When that is not a concern, Morris traversal is able to achieve the optimal time and space complexity. Morris traversal is original designed for in-order traversal, but it can be applied to pre-order traversal as well, though I am not sure if it’s applicable to post-order traversal.

Our demonstration of binary trees here is based on the representation with linked lists.

Examples:

In-order traversal

The goal of reorganization here is to form a binary tree as a thread with the left branch, root, and right branch.

  1. The in-order predecessor of a root it’s the rightmost node of its left branch. Therefore, we reorganize the tree to let the rightmost node of the left branch point to the root.
  2. After that, the root of that left branch becomes the new root of the tree. We then repeat the process from Step 1.
  3. Once the root of the tree has no left branch, we are ready to visit it. We then move on to the right branch of the root and repeat the process from Step 1.
// "root" is the root node of the given binary tree for traversal.
TreeNode *node = root;
while (node)
{
    // Step 1.
    TreeNode *leftRightMost = node->left;
    while (leftRightMost && leftRightMost->right)
    {
        leftRightMost = leftRightMost->right;
    }
    if (leftRightMost)
    {
        // Step 2.
        leftRightMost->right = node;
        TreeNode *left = node->left;
        node->left = NULL; // to avoid the infinite loop.
        node = left;
    }
    else
    {
        // Step 3.
        Visit(node->val);
        node = node->right;
    }
}

Pre-order traversal

The goal of reorganization here is to form a binary tree as a thread with the root, left branch, and right branch.

  1. The pre-order traversal first visits the root of a tree. Since we always start from the root of a binary tree, we just visit it.
  2. Traverse to the rightmost node of the left branch if any and let it point to the right node of the root.
  3. We let the root point to the left branch if any. We then move on to the next node and repeat the process from Step 1. Note that we don’t need to nullify the left pointer of the original root before moving on to the next node, since we have already done with the visit of that original root. Here we still apply such nullification just to form the threaded binary tree completely.
// "root" is the root node of the given binary tree for traversal.
TreeNode *node = root;
while (node)
{
    // Step 1.
    Visit(node);

    // Step 2.
    TreeNode *leftRightmost = node->left;
    while (leftRightmost && leftRightmost->right)
    {
        leftRightmost = leftRightmost->right;
    }
    if (leftRightmost)
    {
        leftRightmost->right = node->right;
    }

    // Step 3.
    if (node->left)
    {
        node->right = node->left;
    }
    node->left = NULL;
    node = node->right;
}

Post-order traversal

I didn’t figure out a way of implementing Morris post-order traversal. A workaround is to derive it from the Morris pre-order traversal (with the sequence of root, right, and left) and then reverse the traversal result.

Contents