Write non-recursive traversal of a binary search tree using constant space and time O (n)

Question

This is not homework, this is an interview question.

The catch is that the algorithm must be constant. I pretty much do not know how to do this without a stack, I would publish what I wrote using the stack, but this has nothing to do.

Here is what I tried: I tried to do a preliminary tour, and I got to the very left node, but I got stuck there. I do not know how to overwrite a backup without a stack / parent pointer.

Any help would be appreciated.

(I mark it as Java since that is convenient for me to use, but it is quite a linguistic agnostic, as you can see.)

Answer 1

I did not think about it completely, but I think it is possible if you are ready to spoil your tree in the process.

Each Node has 2 pointers, so it can be used to represent a doubly linked list. Suppose you go from Root to Root.Left = Current. Now the Root.Left pointer is useless, so assign it Current.Right and go to Current.Left. When you reach the leftmost child, you will have a linked list with trees hanging from some nodes. Now repeat this, repeating the process for each tree that you encounter when you walk

EDIT: thought through. Here's an 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; } } } 

Answer 2

How about traversing the Morris Inorder tree? It is based on the concept of threaded trees, and it changes the tree, but brings it back when it is done.

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

No extra space is used.

Answer 3

If you use a tree with a down pointer and do not have a parent pointer or any other memory, it is impossible to move in constant space.

Perhaps if your binary tree is in an array instead of a pointer-based object structure. But then you can access any node directly. This is a kind of deception ,-)

Answer 4

Here is a shorter version of iluxa original answer . It performs exactly the same node manipulation and printing operations in exactly the same order, but simplified [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] Furthermore, it works even when the root of the node tree does not have a left child.

Answer 5

This is a search tree, so you can always get the next key / entry

You need smth (I have not tested the code, but it is as simple as it is)

 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 is 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; } 

Answer 6

The question title does not mention the absence of a "parent" pointer in node. Although this is not required for BST, many binary tree implementations have a parent pointer. class Node {Node * on the left; Node * on the right; Node * parent; DATA data; };

This is so, drawing a diagram of a tree on paper and drawing with a pencil around a tree, rising and falling on both sides of the edges (during the descent you will remain from the edge, and when you rise, you will be on the right side). Basically, there are 4 states:

• SouthWest: You are on the left side of the edge, going from the parent to his left child.
• NorthEast: transition from left child back to parent
• SouthEast: Transitioning from Parent to Right Child
• NorthWest: transition from the right child to the parent object

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

Answer 7

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

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

Answer 8

minor special case for iluxa answer above

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

Answer 9

This is a binary search tree, so each node can be reached with a series of right / left solutions. Describe this series as 0/1, the least significant bit is the most significant. Thus, the function f (0) means "node, found by accepting the right branch until you find the leaf, f (1) means you need to take one left and right right, f (2) - that is, binary 010 - means accept, then left, then right until you find a sheet. Iterate f (n) starting at n = 0 until you click on each sheet. Ineffective (since you should start at the top of the tree every time), but read-only memory and linear time.

Answer 10

We can cross the binary tree without changing the tree itself (if the nodes have a parent pointer). And this can be done in a 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/