Write a program to compute the in-order traversal of a binary tree using O(1) sp...
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.
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK