9

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

 1 year ago
source link: https://www.coderzheaven.com/2023/06/25/write-a-program-to-compute-the-in-order-traversal-of-a-binary-tree-using-o1-space/?amp%3Butm_medium=rss&%3Butm_campaign=write-a-program-to-compute-the-in-order-traversal-of-a-binary-tree-using-o1-space
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

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.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK