Morris Traversal Inorder Without Stack in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Morris Traversal for inorder tree traversal?

Morris Traversal uses threaded binary trees by temporarily modifying the tree's right pointers to avoid using a stack or recursion, enabling inorder traversal with O(1) extra space.

intermediate

In Morris Traversal, what do we do when the current node has a left child?

We find the rightmost node in the left subtree (predecessor). If its right pointer is null, we set it to point to the current node (threading). If it already points to the current node, we remove the thread and move to the right child.

beginner

Why does Morris Traversal not require a stack or recursion?

Because it temporarily changes the tree structure by creating threads to the inorder successor, allowing traversal without extra memory for stack or recursion.

intermediate

What is the time complexity of Morris Traversal Inorder?

The time complexity is O(n) because each edge is visited at most twice: once to create a thread and once to remove it.

beginner

What happens if the current node has no left child in Morris Traversal?

We print the current node's value and move to its right child directly.

What does Morris Traversal use to avoid stack or recursion?

A Temporary threads in the tree

B Extra stack memory

C Recursion

D Queue data structure

Morris Traversal creates temporary threads (right pointers) to the inorder successor to avoid using stack or recursion.

When finding the predecessor in Morris Traversal, what is the predecessor?

A Leftmost node in the right subtree

B Root node

C Parent node

D Rightmost node in the left subtree

The predecessor is the rightmost node in the current node's left subtree.

What do we do if the predecessor's right pointer is already pointing to the current node?

A Remove the thread and move to right child

B Create a new thread

C Stop traversal

D Move to left child

If the thread exists, we remove it and then move to the right child.

What is the space complexity of Morris Traversal?

A O(log n)

B O(n)

C O(1)

D O(n log n)

Morris Traversal uses O(1) extra space by modifying the tree temporarily.

If a node has no left child, what is the next step in Morris Traversal?

A Move to left child

B Print the node and move to right child

C Create a thread

D Find predecessor

If no left child, print the node and move directly to its right child.

Explain step-by-step how Morris Traversal performs inorder traversal without using a stack or recursion.

Think about how the tree's right pointers are temporarily changed to remember where to go next.

Describe the advantages and potential drawbacks of using Morris Traversal for inorder traversal.

Consider memory usage and tree modification.