Traversing Binary Tree from Root to each Branch

[vluong]

I have a couple of other questions. I need to get all the different combinations in a binary tree and store them into a data structure. For example, in the attached diagram of a binary tree the combinations would be:




1) A, A1, A2, B1, B2
2) A, A1, B1, A2, B2
3) A, A1, B1, B2, A24) A, B1, A1, A2, B2
5) A, B1, A1, B2, A2
6) A, B1, B2, A1, A2

I understand that this is very similar to the preorder traversal, but preorder does not output the parent nodes another time when the node splits into a left and right node. Any suggestions?

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package binarytreetest;
import java.util.ArrayList;
import java.util.Iterator;
/**
 *
 * @author vluong
 */
public class BinaryTreeTest {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
         
        int countA = 0;
        int countB = 0;
        ArrayList listA = new ArrayList();
        ArrayList listB = new ArrayList();
        listA.add("A1");
        listA.add("A2");
        listA.add("A3");
        listB.add("B1");
        listB.add("B2");
        listB.add("B3");
        //listB.add("B1");
        Node root = new Node("START");
        constructTree(root, countA, countB, listA, listB);
        
        //printInOrder(root);
        //printFromRoot(root);

        
        
    }
    
    
    public static class Node{
        private Node left;
        private Node right;
        private String value;
        public Node(String value){
            this.value = value;
        }
    }
    
    public static void constructTree(Node node, int countA, int countB, ArrayList listA, ArrayList listB){
        if(countA < listA.size()){
            if(node.left == null){
                System.out.println("There is no left node. CountA is " + countA);
                System.out.println("Created new node with value: " + listA.get(countA).toString() + " with parent, " 
                        + node.value);
                System.out.println();
                node.left = new Node(listA.get(countA).toString());  
                constructTree(node.left, countA+1, countB, listA, listB);    
            }else{
                System.out.println("There is a left node. CountA + 1 is " + countA+1);
                constructTree(node.left, countA+1, countB, listA, listB);    
            }
        }
        if(countB < listB.size()){
            if(node.right == null){
                System.out.println("There is no right node. CountB is " + countB);
                System.out.println("Created new node with value: " + listB.get(countB).toString() + " with parent, "
                        + node.value);
                System.out.println();
                node.right = new Node(listB.get(countB).toString());
                constructTree(node.right, countA, countB+1, listA, listB); 
            }else{
                System.out.println("There is a right node. CountB + 1 is " + countB+1);
                constructTree(node.right, countA, countB+1, listA, listB);
            }
        }
    }

My second question is, if I need to add another list (listC) and find all the combinations of List A, listB and list C, is it correct to define the node class as

 public static class Node{
        private Node left;
        private Node mid;
        private Node right;
        private String value;
        public Node(String value){
            this.value = value;
        }
    }

Node left = listA, Node mid = listB, Node right = listC

The code for the 3 lists is below.

3 lists (A, B, C):

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package binarytreetest;
import java.util.ArrayList;
/**
 *
 * @author vluong
 */
public class BinaryTreeTest {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
       
        /*
        insert(root, "A1");
        insert(root, "A2");
        insert(root, "B1");
        insert(root, "B2");  
        insert(root, "A2");
       
        * 
        */
        
        int countA = 0;
        int countB = 0;
        int countC = 0;
        ArrayList listA = new ArrayList();
        ArrayList listB = new ArrayList();
        ArrayList listC = new ArrayList();
        listA.add("A1");
        listA.add("A2");
        //listA.add("A3");
        listB.add("B1");
        listB.add("B2");
        //listB.add("B3");
        //listB.add("B1");
        listC.add("C1");
        listC.add("C2");
        
        Node root = new Node("START");
        constructTree(root, countA, countB, countC, listA, listB, listC);
        //ConstructTree(root, countA, countB, listA, listB);
        //ConstructTree(root, countA, countB, listA, listB);
        printInOrder(root);
        //printFromRoot(root);

        
        
    }
    
    
    public static class Node{
        private Node left;
        private Node mid;
        private Node right;
        private String value;
        public Node(String value){
            this.value = value;
        }
    }
    
    public static void constructTree(Node node, int countA, int countB, int countC, ArrayList listA, ArrayList listB, ArrayList listC){
        if(countA < listA.size()){
            if(node.left == null){
                System.out.println("There is no left node. CountA is " + countA);
                System.out.println("Created new node with value: " + listA.get(countA).toString() + " with parent, " 
                        + node.value);
                System.out.println();
                node.left = new Node(listA.get(countA).toString());  
                constructTree(node.left, countA+1, countB, countC, listA, listB, listC);    
            }else{
                System.out.println("There is a left node. CountA + 1 is " + countA+1);
                constructTree(node.left, countA+1, countB, countC, listA, listB, listC);    
            }
        }
        if(countB < listB.size()){
            if(node.mid == null){
                System.out.println("There is no mid node. CountB is " + countB);
                System.out.println("Created new node with value: " + listB.get(countB).toString() + " with parent, "
                        + node.value);
                System.out.println();
                node.mid = new Node(listB.get(countB).toString());
                constructTree(node.mid, countA, countB+1, countC, listA, listB, listC); 
            }else{
                System.out.println("There is a right node. CountB + 1 is " + countB+1);
                constructTree(node.mid, countA, countB+1, countC, listA, listB, listC);
            }
        }
        if(countC < listC.size()){
            if(node.right == null){
                System.out.println("There is no right node. CountC is " + countC);
                System.out.println("Created new node with value: " + listC.get(countC).toString() + " with parent, "
                        + node.value);
                System.out.println();
                node.right = new Node(listC.get(countC).toString());
                constructTree(node.right, countA, countB, countC+1, listA, listB, listC); 
            }else{
                System.out.println("There is a right node. CountC + 1 is " + countC+1);
                constructTree(node.mid, countA, countB, countC+1, listA, listB, listC);
            }
        }
    }

Thank you in advance!

[JosAH]

Two possibilities come to mind:

1) if you have an algorithm that can traverse to each leaf node, add another parameter to that method: a List<Node> object and add the current Node to that list each time you visit a new node (which is 'deeper' in the tree). When you reach a leaf Node the List<Node> contains the path from the root to it.
2) add another element to each Node, pointing to the parent of the Node. For the same method as above, as soon as it reaches a leaf Node, traverse upwards using the parent Nodes and find the path to the root; reverse the path as soon as you reach the root Node.

kind regards,

Jos

[vluong]

Thank you for the help, JosAH!

[JimmyD]

I think extending on Jos.. You can pass a stack as a parameter to the traversal. stack the notes you visit. If you go backwards, pop the nodes out, then every time you reach the end, the stack is a unique combination you want to store.