Inorder traversal of BST without extra space
  • binarysearchtree
  • binarytree
  • inordertraversal
  •   
  • Posted: 4 years ago
  • Edit
  • answers (1)
  • views (3566)

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


Posted Answers

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.

You need to Sign In to post your solution.