Write a program to compute the in-order traversal of a binary tree using O(1) space.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def inorderTraversal(root):
    current = root
    while current:
        if current.left is None:
            print(current.val)  # Process the current node
            current = current.right
        else:
            # Find the predecessor of the current node
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right

            if predecessor.right is None:
                # Establish the temporary link to the current node
                predecessor.right = current
                current = current.left
            else:
                # Remove the temporary link and process the current node
                predecessor.right = None
                print(current.val)  # Process the current node
                current = current.right


# Test the implementation
# Create a binary tree: 1 -> 2 / \ 3 -> 4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("In-order traversal:")
inorderTraversal(root)


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        left = null;
        right = null;
    }
}

public class BinaryTreeInorderTraversal {
    public static void inorderTraversal(TreeNode root) {
        TreeNode current = root;
        while (current != null) {
            if (current.left == null) {
                System.out.print(current.val + " "); // Process the current node
                current = current.right;
            } else {
                // Find the predecessor of the current node
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    // Establish the temporary link to the current node
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // Remove the temporary link and process the current node
                    predecessor.right = null;
                    System.out.print(current.val + " "); // Process the current node
                    current = current.right;
                }
            }
        }
    }

    public static void main(String[] args) {
        // Create a binary tree: 1 -> 2 / \ 3 -> 4   5
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.println("In-order traversal:");
        inorderTraversal(root);
    }
}

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const inorderTraversal = (root) => {
    let current = root;
    while (current) {
        if (current.left === null) {
            console.log(current.val); // Process the current node
            current = current.right;
        } else {
            // Find the predecessor of the current node
            let predecessor = current.left;
            while (predecessor.right !== null && predecessor.right !== current) {
                predecessor = predecessor.right;
            }

            if (predecessor.right === null) {
                // Establish the temporary link to the current node
                predecessor.right = current;
                current = current.left;
            } else {
                // Remove the temporary link and process the current node
                predecessor.right = null;
                console.log(current.val); // Process the current node
                current = current.right;
            }
        }
    }
};

// Test the implementation
// Create a binary tree: 1 -> 2 / \ 3 -> 4   5
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log("In-order traversal:");
inorderTraversal(root);