Python
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightdef 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 5root = 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 5const 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.