Preorder traversal using stack

Question

I wrote the code for an iterative pre-order traversal using stack for binary search tree. Below is the code for same. Please help me verify the correctness of the algorithm. Here t.t is the value of node t.

static void preorder(TreeNode t)
{
    MyConcurrentStack<TreeNode> s = new MyConcurrentStack<TreeNode>();
    while(s.peek()!=null || t!=null)
    {
        if(t!=null)
        {
            System.out.print(t.t+":");
            s.push(t);
            t = t.left;
        }
        else
        {
            t = s.pop();
            t = t.right;
        }
    }
}

Answer 1

There are a few points that can be critizised.

1. The method signature suggests that the architecture of the system isn't well-designed. Traversal of a Tree should likely be encapsulated in an Iterator class. In that case, the stack would be a private field of the iterator, and the actual code would use a foreach loop.

   for (TreeNode node : tree)
     System.out.print(node.t + ":");
   

   (preorder iteration is a good default)

2. Even if we let the design of your classes as they are, your implementation could be improved.

Single-letter variable names should be avoided. True, there are only two variables in your method, but using node and stack would be so much less cryptic.

The stack does not have to be concurrent, because it is not shared accross multiple threads. The vanilla java.util.Stack should work just fine. If you care about concurrency, you should rather worry about the tree nodes. What happens when a node was stored on the stack, but removed from the tree before the right child can be consumed by your code? Make sure the nodes aren't mutated until you visited them.

The body of your loop does not have a single comment although the stack manipulation may not be totally obvious to everybody (incl. you).

If you are optimizing for readability and not for space, I'd strongly suggest a recursive solution. This also makes writing correct code much easier:

static void preorder(TreeNode node) {
  if (node == null) return;

  System.out.println(node.t + ":");

  preorder(node.left);
  preorder(node.right);
}

(Not that your code was incorrect, this is just much easier to verify).

Next, I would like to reorder the parts of your loop to make it more obvious what is happening:

while (true)
{
    // check if we have to pop a value of the stack
    while (node == null) {
      if (stack.empty()) return;
      node = stack.pop().right;
    }

    System.out.print(node.t + ":");

    stack.push(node);  // store the node to continue the right path later
    node = node.left;
}

Note: If we use the java.util.Stack, then peek() could throw an EmptyStackException. We should rather use the empty() method which returns a boolean.

I think it would be more elegant to put the right childs on the stack, not the nodes which we already visited. We should also test whether these are null before adding them to the stack. This would keep the stack smaller:

while (true)
{
    // check if we have to pop a value of the stack WITHOUT LOOPING:
    // It is guaranteed that there never is a null node on the stack.
    if (node == null) {
      if (stack.empty()) return;
      node = stack.pop();
    }

    System.out.print(node.t + ":");

    // store the right node to continue there later
    if (node.right != null) stack.push(node.right);

    node = node.left;
}

I am not too comfortable with a while (true) loop, but the alternatives would mean slight code duplication (e.g. in your original code, you have two t!=null tests.)

Finally, you likely want to print a newline after this iteration. (In that case, the return should be a break).

Answer 2

Here is my latest implementation:

public class Tree<K> implements Iterable<K>
{
    private TreeNode<K> root;
    static class TreeNode<K>
    {
        K k;
        TreeNode<K> left;
        TreeNode<K> right;
        public TreeNode(K k)
        {
            this.k = k;
        }
    }

    public void insert(K k)
    {
        Comparable cc = (Comparable)k;
        if(root == null)
        {
            root = new TreeNode<K>(k);
        }
        else
        {
            TreeNode temp = root;
            TreeNode parent = root;
            while(temp!=null)
            {
                parent = temp;
                Comparable c = (Comparable)temp.k;
                if(c.compareTo(cc) < 0)
                {
                    temp =temp.right;
                }
                else
                {
                    temp = temp.left;
                }
            }
            Comparable c = (Comparable)parent.k;
            if(c.compareTo(cc) > 0)   
            {
                parent.left = new TreeNode(k);
            }
            else
            {
                parent.right = new TreeNode(k);
            }
        }
    }

    @Override
    public Iterator<K> iterator()
    {
        return new MyIterator<K>();
    }
    private class MyIterator<K> implements Iterator<K>
    {
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode<K> t = (TreeNode<K>) root;

        @Override
        public boolean hasNext()
        {
            if(s.peek()!=null || t!=null)
            {
                return true;
            }
            return false;
        }

        @Override
        public K next() 
        {
            while(s.peek() !=null || t!=null)
            {
                if(t!=null)
                {
                    s.push(t);
                    t = t.left;
                }
                else
                {
                    t = s.pop();
                    TreeNode<K> temp = t;
                    t = t.right;
                    return temp.k;
                }
            }
            return null;
        }

        @Override
        public void remove() 
        {

        }

    }
}