Morris Traversal Inorder Without Stack in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Morris Inorder Traversal on a Simple Tree

What is the output of the Morris inorder traversal on the following binary tree?

Tree structure:
2
/ \
1 3

Assume the traversal prints node values separated by spaces.

DSA Go

package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func morrisInorder(root *Node) {
    current := root
    for current != nil {
        if current.Left == nil {
            fmt.Print(current.Val, " ")
            current = current.Right
        } else {
            pre := current.Left
            for pre.Right != nil && pre.Right != current {
                pre = pre.Right
            }
            if pre.Right == nil {
                pre.Right = current
                current = current.Left
            } else {
                pre.Right = nil
                fmt.Print(current.Val, " ")
                current = current.Right
            }
        }
    }
}

func main() {
    root := &Node{Val: 2}
    root.Left = &Node{Val: 1}
    root.Right = &Node{Val: 3}
    morrisInorder(root)
}

A 1 2 3

B 2 1 3

C 3 2 1

D 1 3 2

💡 Hint

Inorder traversal visits left subtree, then node, then right subtree.

Morris inorder traversal visits nodes in ascending order for a BST. The tree nodes are 1, 2, 3. So output is '1 2 3 '.

❓ Predict Output

intermediate

Output of Morris Inorder Traversal on a Tree with Only Left Children

What is the output of the Morris inorder traversal on this tree?

Tree structure:
4
/
3
/
2
/
1

Assume the traversal prints node values separated by spaces.

DSA Go

package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func morrisInorder(root *Node) {
    current := root
    for current != nil {
        if current.Left == nil {
            fmt.Print(current.Val, " ")
            current = current.Right
        } else {
            pre := current.Left
            for pre.Right != nil && pre.Right != current {
                pre = pre.Right
            }
            if pre.Right == nil {
                pre.Right = current
                current = current.Left
            } else {
                pre.Right = nil
                fmt.Print(current.Val, " ")
                current = current.Right
            }
        }
    }
}

func main() {
    root := &Node{Val: 4}
    root.Left = &Node{Val: 3}
    root.Left.Left = &Node{Val: 2}
    root.Left.Left.Left = &Node{Val: 1}
    morrisInorder(root)
}

A 1 3 2 4

B 1 2 3 4

C 4 3 2 1

D 2 1 3 4

💡 Hint

Inorder traversal visits nodes from smallest to largest in this left-skewed tree.

The inorder traversal visits nodes from leftmost (1) up to root (4) in ascending order.

🔧 Debug

advanced

Identify the Bug in Morris Traversal Code

The following Go code attempts Morris inorder traversal but produces incorrect output. What is the bug?

DSA Go

func morrisInorder(root *Node) {
    current := root
    for current != nil {
        if current.Left == nil {
            fmt.Print(current.Val, " ")
            current = current.Right
        } else {
            pre := current.Left
            for pre.Right != nil {
                pre = pre.Right
            }
            if pre.Right == nil {
                pre.Right = current
                current = current.Left
            } else {
                pre.Right = nil
                fmt.Print(current.Val, " ")
                current = current.Right
            }
        }
    }
}

A The inner loop misses checking if pre.Right == current, causing infinite loop or wrong threading.

B The code should print current.Val before setting pre.Right = current.

C The code incorrectly sets pre.Left instead of pre.Right.

D The code should move current to current.Right before printing current.Val.

💡 Hint

Check the condition inside the inner while loop that finds the predecessor.

The inner loop must check pre.Right != nil AND pre.Right != current to avoid infinite loops and correctly restore tree structure.

🧠 Conceptual

advanced

Why Morris Traversal Uses Threaded Links

Why does Morris inorder traversal create temporary links (threads) from the inorder predecessor to the current node?

A To permanently modify the tree structure for faster future traversals.

B To store node values temporarily during traversal.

C To avoid using a stack or recursion by remembering where to return after visiting left subtree.

D To balance the tree dynamically during traversal.

💡 Hint

Think about how recursion or stack remembers the path back to a node.

Morris traversal uses threads to remember the return path without extra memory, enabling O(1) space traversal.

🚀 Application

expert

Count Nodes Using Morris Traversal Without Extra Space

Using Morris inorder traversal, how can you count the total number of nodes in a binary tree without using recursion or a stack?

A Count nodes by traversing only right children and ignoring left children.

B Count nodes by incrementing counter only when creating a thread link.

C Count nodes by incrementing counter only when removing a thread link.

D Traverse the tree with Morris inorder and increment a counter each time a node is visited (printed).

💡 Hint

Each node is visited exactly once in inorder traversal.

In Morris traversal, each node is printed exactly once when visited. Counting these visits gives total nodes.