Non-recursive method to find all nodes of each vine of Binary Search Tree using a stack

Question

I am trying to create one method that will find all nodes from the paths from the root to each leaf in a binary search tree and store them in an array. So far I have made a rediculous method that works fine if the right side of the root doesn't have more than one node that's parent to two nodes. It took me a long time to figure out what was wrong, but if my current method is to work I have to know the tree, and that's just stupid.

This is basically what I'm trying to do:

Output: [[8, 3, 1],[8 ,3 ,6 ,4],[8, 3, 6, 7],[8, 10, 14, 13]]

I want to avoid recursion and rather use stack. But I don't see how I can "control" which nodes to pop from the stack.. What if they have subtrees with subtrees.

Answer 1

Something like this:

function Explore(node, currentPath)
   Add node to the currentPath

   If node has any Children
     If node has a left child
       Explore(left child, currentPath)
     if node has a right child  
       Explore(right child, currentPath)
   Else
     Node is a leaf node, report currentPath as a result.

   Remove the last node from currentPath
end

Answer 2

http://en.wikipedia.org/wiki/Tree_traversal#Preorder

Wikipedia explains it better than I ever could. You want Depth First traversal, and when you hit a leaf, record the entire path taken so far.

Answer 3

See Iterative DFS vs Recursive DFS and different elements order for both recursive and iterative (using a stack) DFS implementations.

Edit:

It's really quite readable if you ignore the c++ specific syntax, but here's a brief pseudocodish description.

create a stack of nodes
push root node of the tree on the stack. 
while (the stack is not empty) {
   pop the top of the stack, call it 'node' 
   if (we have not already marked 'node') {
     print the name of that node
     mark that node
     push any children of that node onto the stack
   } 
} 

What you will need, that isn't required in the recursive method is a way of keeping track of which nodes you've already visited (that's what's meant by 'marking' a node). This can either be a property of the node itself, or you can maintain a separate data structure. A Java HashSet would work well for this.

Answer 4

If you are not going to do recursion, you have to store explicitly in a stack the sort of data that would be implied by where a call was done or in local variables in a recursive solution. In this case, I used a couple of booleans to indicate whether the left subtree has been done and whether the right subtree has been done.

I could not quite bring myself to do it all in one method. I do use a separate method to extract the list of node labels from the stack. Also, to save carrying around a separate label list, I'm not treating it strictly as a stack. I think the changes to make it a strict stack are fairly obvious. I've only commented the core code. Feel free to ask if anything else is unclear.

I do want to emphasize that this is not a design I recommend. I would use recursion, which I think would result in simpler code. I have also not spent a lot of time polishing it.

  import java.util.Stack;

  public class Bad {
    public static void main(String[] args) {
      TreeNode root;
      boolean firstLeaf = true;
      root = makeTree();
      Stack<StackNode> stack = new Stack<StackNode>();
      stack.push(new StackNode(root));
      System.out.print("[");
      while (stack.size() > 0) {
        // Decide what to do next with the top element
        StackNode top = stack.lastElement();
        if (top.tn == null) {
          // Nothing to do for a null subtree
          stack.pop();
        } else {
          if (top.tn.left == null && top.tn.right == null) {
            // leaf element, print it out and pop it.
            if(!firstLeaf) {
              System.out.print(",");
            }
            firstLeaf = false;
            System.out.print("[" + getLabelList(stack) + "]");
            stack.pop();
          } else {
            if (top.leftDone) {
              if (!top.rightDone) {
                stack.push(new StackNode(top.tn.right));
                top.rightDone = true;
              } else {
                // Done both subtrees
                stack.pop();
              }
            } else {
              stack.push(new StackNode(top.tn.left));
              top.leftDone = true;
            }
          }
        }
      }
      System.out.println("]");
    }

    private static class StackNode {
      TreeNode tn;
      boolean leftDone;
      boolean rightDone;

      public StackNode(TreeNode tn) {
        this.tn = tn;
      }
    }

    private static String getLabelList(Stack<StackNode> in) {
      String result = "";
      for (StackNode node : in) {
        if (result.length() > 0) {
          result += ", ";
        }
        result += node.tn.label;
      }
      //System.out.print("getLabelList: " + result);
      return result;
    }

    private static TreeNode makeTree() {
      TreeNode l;
      TreeNode r;
      l = new TreeNode(4, null, null);
      r = new TreeNode(7, null, null);
      r = new TreeNode(6, l, r);
      l = new TreeNode(1, null, null);
      l = new TreeNode(3, l, r);
      r = new TreeNode(14, new TreeNode(13, null, null), null);
      r = new TreeNode(10, null, r);
      return (new TreeNode(8, l, r));
    }
  }

  class StackNode {
    TreeNode current;
    boolean leftSubtreeDone;
  }

  class TreeNode {
    int label;
    TreeNode left;
    TreeNode right;

    public TreeNode(int label, TreeNode left, TreeNode right) {
      this.label = label;
      this.left = left;
      this.right = right;
    }
  }