Explain Morris inorder tree traversal without using stacks or recursion

by

If I am reading the algorithm right, this should be an example of how it works:

     X
   /   \
  Y     Z
 / \   / \
A   B C   D

First, X is the root, so it is initialized as current. X has a left child, so X is made the rightmost right child of X‘s left subtree — the immediate predecessor to X in an inorder traversal. So X is made the right child of B, then current is set to Y. The tree now looks like this:

    Y
   / \
  A   B
       \
        X
       / \
     (Y)  Z
         / \
        C   D

(Y) above refers to Y and all of its children, which are omitted for recursion issues. The important part is listed anyway.
Now that the tree has a link back to X, the traversal continues…

 A
  \
   Y
  / \
(A)  B
      \
       X
      / \
    (Y)  Z
        / \
       C   D

Then A is outputted, because it has no left child, and current is returned to Y, which was made A‘s right child in the previous iteration. On the next iteration, Y has both children. However, the dual-condition of the loop makes it stop when it reaches itself, which is an indication that it’s left subtree has already been traversed. So, it prints itself, and continues with its right subtree, which is B.

B prints itself, and then current becomes X, which goes through the same checking process as Y did, also realizing that its left subtree has been traversed, continuing with the Z. The rest of the tree follows the same pattern.

No recursion is necessary, because instead of relying on backtracking through a stack, a link back to the root of the (sub)tree is moved to the point at which it would be accessed in a recursive inorder tree traversal algorithm anyway — after its left subtree has finished.

More Related Contents:

  1. What is the fastest way to change a key of an element inside std::map
  2. Why can’t I use a “break” statement inside a ternary conditional statement in C++?
  3. “unpacking” a tuple to call a matching function pointer
  4. shared_ptr to an array : should it be used?
  5. C++ deprecated conversion from string constant to ‘char*’
  6. Why does omission of “#include ” only sometimes cause compilation failures?
  7. strptime() equivalent on Windows?
  8. How much is too much with C++11 auto keyword?
  9. Is it safe to use -1 to set all bits to true?
  10. How to concatenate a std::string and an int
  11. Why does C++ allow us to surround the variable name in parentheses when declaring a variable?
  12. vector size – 1 when size is 0 in C++
  13. What does std::match_results::size return?
  14. Are variable length arrays there in c++?
  15. How to get list of files with a specific extension in a given folder?
  16. Escape sequence \f – form feed – what exactly is it?
  17. Non-copyable elements in vector
  18. Retrieving file descriptor from a std::fstream [duplicate]
  19. How to atomically update a maximum value?
  20. Windows/C++: Is it possible to find the line of code where exception was thrown having “Exception Offset”
  21. Multithreaded Memory Allocators for C/C++
  22. Can I return in void function?
  23. Template typedefs – What’s your work around?
  24. Are there in x86 any instructions to accelerate SHA (SHA1/2/256/512) encoding?
  25. Constructor initialization Vs assignment
  26. Why does destructor disable generation of implicit move methods?
  27. Is there a way to do a #define inside of another #define?
  28. Is there a C++11 syntax file for vim?
  29. Templates: template function not playing well with class’s template member function [duplicate]
  30. How does the friend keyword (Class/Function) break encapsulation in C++?

Leave a Comment