Morris Traversal Inorder Without Stack in DSA Go - Build from Scratch

Morris Traversal Inorder Without Stack

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to visit each family member in order from left to right without using extra memory like a stack or recursion.

🎯 Goal: Build a Go program that performs an inorder traversal of a binary tree using Morris Traversal technique, which uses no stack or recursion, and prints the node values in order.

📋 What You'll Learn

Define a binary tree node struct called Node with Val, Left, and Right fields

Create a sample binary tree with exact nodes and structure

Implement Morris inorder traversal without using stack or recursion

Print the node values in inorder sequence separated by spaces

💡 Why This Matters

🌍 Real World

Morris traversal is useful in systems with limited memory where recursion or stack usage is costly, such as embedded systems or memory-constrained devices.

💼 Career

Understanding Morris traversal helps in optimizing tree traversal algorithms and is valuable for software engineers working on performance-critical applications or low-level system programming.

1

Create the binary tree structure and nodes

Define a struct called Node with fields Val int, Left *Node, and Right *Node. Then create a binary tree with root node value 1, root's left child value 2, root's right child value 3, left child's left child value 4, and left child's right child value 5.

DSA Go

// Define Node struct and create the binary tree nodes
// Your code here

Hint

Start by defining the Node struct with the three fields. Then create the root node and assign its left and right children as described.

2

Add a variable to hold the current node during traversal

Inside the main function, create a variable called current and set it equal to root. This will be used to traverse the tree.

DSA Go

package main

import "fmt"

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

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

    // Create current variable for traversal
    // Your code here
}

Hint

Just assign current to root inside main.

3

Implement Morris inorder traversal logic

Write a for loop that runs while current != nil. Inside the loop, if current.Left is nil, print current.Val followed by a space and move current to current.Right. Otherwise, find the inorder predecessor of current by moving to current.Left and then repeatedly to the right child until the right child is nil or current. If the predecessor's right child is nil, set it to current and move current to current.Left. If the predecessor's right child is current, set it back to nil, print current.Val followed by a space, and move current to current.Right.

DSA Go

package main

import "fmt"

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

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

    current := root

    // Implement Morris inorder traversal loop
    // Your code here
}

Hint

Use a for loop with current != nil. Inside, check if current.Left is nil. If yes, print and move right. Otherwise, find the predecessor and create or remove the thread accordingly.

4

Print the inorder traversal result

Add a newline print statement after the Morris traversal loop to move the cursor to the next line.

DSA Go

package main

import "fmt"

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

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

    current := root

    for current != nil {
        if current.Left == nil {
            fmt.Printf("%d ", current.Val)
            current = current.Right
        } else {
            predecessor := current.Left
            for predecessor.Right != nil && predecessor.Right != current {
                predecessor = predecessor.Right
            }
            if predecessor.Right == nil {
                predecessor.Right = current
                current = current.Left
            } else {
                predecessor.Right = nil
                fmt.Printf("%d ", current.Val)
                current = current.Right
            }
        }
    }

    // Print newline after traversal
    // Your code here
}

Hint

After the loop finishes printing all node values with spaces, print a newline using fmt.Println() to end the output cleanly.