Write a non-recursive traversal of a Binary Search

问题:

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.)

回答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;
    }
  }
}

回答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.

回答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 ;-)

回答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.

回答5:

It's a a search tree, so you can always get the next key/entry

You need smth like (I didn't test the code, but it's as simple as it gets)

java.util.NavigableMap<K, V> map=...
for (Entry<K, V> e = map.firstEntry(); e!=null; e = map.higherEntry(e.getKey())) {
  process(e)
}

for clarity this is higherEntry, so it's not recursive. There you have it :)

final Entry<K,V> getHigherEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else {
            if (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}

回答6:

The title of the question doesn't mention the lack of a "parent" pointer in the node. Although it isn't necessarily required for BST, many binary tree implementations do have a parent pointer. class Node { Node* left; Node* right; Node* parent; DATA data; };

It this is the case, imaging a diagram of the tree on paper, and draw with a pencil around the tree, going up and down, from both sides of the edges (when going down, you'll be left of the edge, and when going up, you'll be on the right side). Basically, there are 4 states:

1. SouthWest: You are on the left side of the edge, going from the parent its left child
2. NorthEast: Going from a left child, back to its parent
3. SouthEast: Going from a parent to a right child
4. NorthWest: Going from a right child, back to its parent

Traverse( Node* node )
{
    enum DIRECTION {SW, NE, SE, NW};
    DIRECTION direction=SW;

    while( node )
    {
        // first, output the node data, if I'm on my way down:
        if( direction==SE or direction==SW ) {
            out_stream << node->data;
        }

        switch( direction ) {
        case SW:                
            if( node->left ) {
                // if we have a left child, keep going down left
                node = node->left;
            }
            else if( node->right ) {
                // we don't have a left child, go right
                node = node->right;
                DIRECTION = SE;
            }
            else {
                // no children, go up.
                DIRECTION = NE;
            }
            break;
        case SE:
            if( node->left ) {
                DIRECTION = SW;
                node = node->left;
            }
            else if( node->right ) {
                node = node->right;
            }
            else {
                DIRECTION = NW;
            }
            break;
        case NE:
            if( node->right ) {
                // take a u-turn back to the right node
                node = node->right;
                DIRECTION = SE;
            }
            else {
                node = node->parent;
            }
            break;
        case NW:
            node = node->parent;
            break;
        }
    }
}

回答7:

Accepted answer needs the following change otherwise it will not print the tree where the BST only has one node

if (current == NULL && root != NULL)
   print(root);

回答8:

minor special case for iluxa's answer above

if(current== null)
        {
            current = root;
            parent = current.Right;
            if(parent != null)
            {
                current.Right = parent.Left;
                parent.Left = current;
            }
        }

回答9:

It's a binary search tree, so every node can be reached by a series of right/left decision. Describe that series as 0/1, least-significant bit to most-significant. So the function f(0) means "the node found by taking the right-hand branch until you find a leaf; f(1) means take one left and the rest right; f(2) -- that is, binary 010 -- means take a right, then a left, then rights until you find a leaf. Iterate f(n) starting at n=0 until you have hit every leaf. Not efficient (since you have to start at the top of the tree each time) but constant memory and linear time.

回答10:

We can traverse the binary tree without modifying the tree itself (provided nodes have parent pointer). And it can be done in constant space. I found this useful link for the same http://tech.technoflirt.com/2011/03/04/non-recursive-tree-traversal-in-on-using-constant-space/