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

By | June 25, 2023

Python

```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)
﻿
```

Java

```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);
}
}

```

Javascript

```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);

```

These implementations use the Morris Traversal algorithm to perform in-order traversal without using any additional space other than O(1). The algorithm establishes temporary links between nodes and their predecessors, allowing efficient traversal and processing of the tree nodes.

Note: The code examples assume that the tree nodes have a `val`, `left`, and `right` property to represent the value, left child, and right child of each node, respectively.