### Inorder traversal of BST without extra space binarysearchtree binarytree inordertraversal    Posted: 5 years ago Edit answers (1) views (4145)

Design an algorithm to perform inorder traversal of a binary search tree using only a constant amount of extra space.

 Posted: 5 years ago Updated: 5 years ago 0 0 Edit We can use $$Morris\ Traversal$$ to perform inorder traversal of a binary search tree using only a constant amount of extra space. Initialize current = root. While (current node is not null) If (Current node has no left child) Print current node's data. Go to its right child. else Make the current node as right child of the rightmost node in current's left subtree. Go to the left child. public static void inOrderTraversalWOSpace(Node root) { if (root == null) return; Node previous, current; current = root; while (current != null) { if (current.left == null){ System.out.println(current.data); current = current.right; }else{ /* Find the inorder predecessor of current */ previous = current.left; while (previous.right != null & & previous.right != current) previous = previous.right) ; /* Make current as right child of its inorder predecessor */ if (previous.right == null) { previous.right = current; current = current.left; }else { /* Restore the original tree : Fix the right child of predecssor */ previous.right = null; System.out.println(current.data); current = current.right; } } } }Running time = $$O(n)$$ since every node is visited once and there is constant amount of operations in each iteration.