Write a non-recursive traversal of a Binary Search Tree using constant space and O(n) run time

Question

This is not homework, this is an interview question.

The catch here is that the algorithm should be constant space. I'm pretty clueless on how to do this without a stack, I'd post what I've written using a stack, but it's not relevant anyway.

Here's what I've tried: I attempted to do a pre-order traversal and I got to the left-most node, but I'm stuck there. I don't know how to "recurse" back up without a stack/parent pointer.

Any help would be appreciated.

(I'm tagging it as Java since that's what I'm comfortable using, but it's pretty language agnostic as is apparent.)

Solution 1

I didn't think it through entirely, but i think it's possible as long as you're willing to mess up your tree in the process.

Every Node has 2 pointers, so it could be used to represent a doubly-linked list. Suppose you advance from Root to Root.Left=Current. Now Root.Left pointer is useless, so assign it to be Current.Right and proceed to Current.Left. By the time you reach leftmost child, you'll have a linked list with trees hanging off of some nodes. Now iterate over that, repeating the process for every tree you encounter as you go

EDIT: thought it through. Here's the algorithm that prints in-order:

void traverse (Node root) {
  traverse (root.left, root);
}

void traverse (Node current, Node parent) {
  while (current != null) {
    if (parent != null) {
      parent.left = current.right;
      current.right = parent;
    }

    if (current.left != null) {
      parent = current;
      current = current.left;
    } else {
      print(current);
      current = current.right;
      parent = null;
    }
  }
}

Solution 2

How about Morris Inorder tree traversal? Its based on the notion of threaded trees and it modifies the tree, but reverts it back when its done.

Linkie: http://geeksforgeeks.org/?p=6358

Doesn't use any extra space.

Solution 3

If you are using a downwards pointer based tree and don't have a parent pointer or some other memory it is impossible to traverse in constant space.

It is possible if your binary tree is in an array instead of a pointer-based object structure. But then you can access any node directly. Which is a kind of cheating ;-)

Solution 4

Here's a shorter version iluxa's original answer. It runs exactly the same node manipulation and printing steps, in exactly the same order — but in a simplified manner [1]:

void traverse (Node n) {
  while (n) {
    Node next = n.left;
    if (next) {
      n.left = next.right;
      next.right = n;
      n = next;
    } else {
      print(n);
      n = n.right;
    }
  }
}

[1] Plus, it even works when the tree root node has no left child.

View more solutions