Ternary Search Tree - Iterative Traversal

Question

I am trying to traverse a ternary search tree iteratively. I am trying to traverse it using the same techniques as used for a binary search tree, keep a stack, push a node, pop it, and push its children.

This way, all the nodes are visited, but i am not sure how can i keep track of what Strings does the tree contain.

I have a recursive code for traversal :

public void traverse(TernaryTreeNode r, String str)
    {
        if (r != null)
        {
            traverse(r.left, str);

            str = str + r.data;
            if (r.isEnd)
                al.add(str);

            traverse(r.middle, str);
            str = str.substring(0, str.length() - 1);

            traverse(r.right, str);
        }
    }

I wish to rewrite an iterative implementation. This is the current code :

public void iterativePreorder(TernaryTreeNode node) {

        // Base Case
        if (node == null) {
            return;
        }

        // Create an empty stack and push root to it
        Stack<TernaryTreeNode> nodeStack = new Stack<TernaryTreeNode>();
        nodeStack.push(root);
        String str = "";

        while (nodeStack.empty() == false) {

            // Pop the top item from stack and print it
            TernaryTreeNode mynode = nodeStack.peek();
            nodeStack.pop();
            str+= mynode.data;
            if(mynode.isEnd){
                al.add(str); //al is an ArrayList of strings
            }

            // Push right and left children of the popped node to stack
            if (mynode.right != null) {
                nodeStack.push(mynode.right);
            }

            if (mynode.middle != null) {
                nodeStack.push(mynode.middle);
            }
            else{
                str = "";
            }

            if (mynode.left != null) {
                nodeStack.push(mynode.left);
            }


        }

    } 

based on the isEnd property, i am able to know whether the current node denotes an End of String, and so i add the str to the arraylist. (the isEnd may or may not be a leaf node). but i am not able to define the logic for getting all strings, using str.

This is the TernaryTreeNode class :

public class TernaryTreeNode {

    char data;
    boolean isEnd;
    TernaryTreeNode left, middle, right;

    public TernaryTreeNode(char data){
        this.data = data;
        this.isEnd = false;
        this.left = this.middle = this.right = null;
    }
}

here is a visual example : http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/

Answer 1

You may consider keeping another Stack to keep track of the string from the parent or use the same Stack with a paired class.

class TernaryPair {
  TernaryTreeNode node;
  String fromParent;
}

Root element put into the stack with an empty string. Whenever you push a string into the stack you also push the string from the parent.

TernaryPair mypair = nodeStack.pop();
str+= mypair.fromParent + mypair.node.data;
if(mypair.node.isEnd){
  al.add(str); //al is an ArrayList of strings
}

and when pushing to the stack

if (mypair.node.right != null) {
  TernaryPair newPair = new TernaryPair();
  newPair.node = mypair.node.right;
  newPair.fromParent = str;
  nodeStack.push(newPair);
}

PS: Stack pop() method will remove and return you the element at the top of the stack. A single call is enough.

TernaryTreeNode mynode = nodeStack.peek();
nodeStack.pop();

-->

TernaryTreeNode mynode = nodeStack.pop();