Results 1 to 4 of 4
  1. #1
    vluong is offline Member
    Join Date
    Mar 2012
    Posts
    2
    Rep Power
    0

    Default Traversing Binary Tree from Root to each Branch

    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:

    Traversing Binary Tree from Root to each Branch-binarytree.png


    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?

    Java Code:
    /*
     * 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

    Java Code:
     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):

    Java Code:
    /*
     * 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!

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,436
    Blog Entries
    7
    Rep Power
    20

    Default Re: Traversing Binary Tree from Root to each Branch

    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
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    vluong is offline Member
    Join Date
    Mar 2012
    Posts
    2
    Rep Power
    0

    Default Re: Traversing Binary Tree from Root to each Branch

    Thank you for the help, JosAH!

  4. #4
    JimmyD is offline Member
    Join Date
    Oct 2011
    Location
    New Jersey
    Posts
    44
    Rep Power
    0

    Default Re: Traversing Binary Tree from Root to each Branch

    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.

Similar Threads

  1. Binary Tree Help - Find the largest sub-tree
    By joshhazel in forum New To Java
    Replies: 2
    Last Post: 01-30-2012, 02:08 AM
  2. binary tree
    By Dedo in forum Advanced Java
    Replies: 15
    Last Post: 05-26-2011, 09:11 PM
  3. Help: traversing huffman tree
    By Reploids in forum New To Java
    Replies: 0
    Last Post: 05-24-2011, 09:42 AM
  4. binary tree
    By ryamz in forum New To Java
    Replies: 2
    Last Post: 08-12-2010, 02:45 AM
  5. Replies: 0
    Last Post: 04-04-2010, 07:40 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •