2
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Agree in general but will question for (TreeNode node : tree) your varible tree seem to suggest that user should pass some kind of collection of nodes however a Node itself is sufficient and rarely if ever you will accross a collection of nodes for traversal. \$\endgroup\$ – Shahzeb Jun 1 '15 at 0:09
-1
\$\begingroup\$

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() 
        {

        }

    }
}
\$\endgroup\$
  • \$\begingroup\$ In insert(), your comparisons should be consistent. You have if(c.compareTo(cc) < 0), and later if(c.compareTo(cc) > 0). Better to make them the same. \$\endgroup\$ – 200_success Aug 12 '13 at 11:08
  • \$\begingroup\$ You should require K to implement Comparable<K>. Then you won't have to cast to Comparable everywhere. \$\endgroup\$ – 200_success Aug 12 '13 at 11:26
  • \$\begingroup\$ This does not constitute a good answer, as it is not attempting to review the original code. Please edit your answer to explain what you improved and why. \$\endgroup\$ – Phrancis Mar 28 '17 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.