This discussion is archived
3 Replies Latest reply: Mar 29, 2012 1:48 PM by marlin RSS

Traverse a binary tree from root to every branch

917249 Newbie
Currently Being Moderated
I have a couple of other questions. I need to get all the different combinations of a binary tree and store them into a data structure. For the example in the code below, the combinations would be:

1) Start, A1, A2, A3, B1, B2, B3
2) Start, A1, A2, B1, A3, B2, B3
3) Start, A1, A2, B1, B2, A3, B3
4) Start, A1, A2, B1, B2, B3, A3
5) Start, A1, B1, A2, A3, B2, B3
etc.

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!
  • 1. Re: Traverse a binary tree from root to every branch
    EJP Guru
    Currently Being Moderated
    preorder does not output the parent nodes another time when the node splits into a left and right node.
    Correct.
    Any suggestions?
    Your samples don't do that either. Why do you think you want it? and if so why don't your samples show it?
    My second question is, if I need to add another list (listC)
    Add it to what?
    and find all the combinations of List A, listB and list C, is it correct to define the node class ...
    No idea. You haven't defined the problem adequately yet.
  • 2. Re: Traverse a binary tree from root to every branch
    917249 Newbie
    Currently Being Moderated
    Thanks for the response. I need to output all the paths from the root to the end of each branch. I am unable to do that. I am trying to manipulate the preorder traversal to do that without success. For example, I need to output: Root -> child.left -> end of branch, which is one path. Then I need to output: Root -> child.right -> end of branch. If I use preorder traversal, the Root on the first path will print, but the Root on the second path will not print. How can I print both paths.

    In regards to list C, I need to add it to the tree and develop all combinations from list A, list B , and list C. To add list C can I just add a middle node, in addition to the left and right nodes of the Node class? Is this the correct approach? Thanks in advance.
  • 3. Re: Traverse a binary tree from root to every branch
    marlin Newbie
    Currently Being Moderated
    It looks to me like you are interleaving two lists. It looks like you are doing this while leaving the two subsequences in their original order.

    If that is in fact what you are doing, then this is just a combinatorics problem. Here is psuedo code (NOT java!)
    List path = new List(); 
    
    show(List A, int a, List B, int b, path){
      if(a >= A.length() && b >= b.length()){
        spew(path);
      } else {
        if(a < A.length()){path.push(A[a]); show(A,a+1,B,b,); path.pop();}
        if(b < B.length()){path.push(B); show(A,a,B,b+1,); path.pop();}
    }
    }

    show(A, 0, B, 0);

    In order to interleave 3 lists, you would add C and c arguments to the function and you would add one more line in the else block.

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points