CODEWITHSUNDEEP
javatreebinary-tree
loknath
loknath

Reputation: 758

print all root to leaf paths in a binary tree

i am trying to print all root to leaf paths in a binary tree using java. 

public void printAllRootToLeafPaths(Node node,ArrayList path) 
{
    if(node==null)
    {
        return;
    }
    path.add(node.data);

    if(node.left==null && node.right==null)
    {
        System.out.println(path);
        return;
    }
    else
    {
        printAllRootToLeafPaths(node.left,path);
        printAllRootToLeafPaths(node.right,path);
    }      
}

In main method:

 bst.printAllRootToLeafPaths(root, new ArrayList());

But its giving wrong output.

given tree:

   5
  / \
 /   \
1     8
 \    /\
  \  /  \
  3  6   9

Expected output:

[5, 1, 3]

[5, 8, 6]

[5, 8, 9]

But the output produced:

[5, 1, 3]

[5, 1, 3, 8, 6]

[5, 1, 3, 8, 6, 9]

Can some one figure it out...

Upvotes: 18

Views: 24345

Answers (12)

Arthour Martirosyan
Arthour Martirosyan

Reputation: 11

It is written with JS but You can gain the logic.

function dive(t, res, arr) {
        if(t.value != null && t.value != undefined) {
            res = res ? `${res}->${t.value}`: `${t.value}`;
        }
        if(t.left) {
            dive(t.left, res, arr );
        } 
        if(t.right) {
            dive(t.right, res, arr );
        } 
        if(!t.left && !t.right) {
            console.log(res)
            arr.push(res);
            return;
        }
}

function getPaths(t) {
    let arr = [];
    if(!t.left && !t.right) {
        t.value != null && t.value != undefined && arr.push(`${t.value}`);
        console.log(arr)
        return arr;
    }
    dive(t, null, arr);
    console.log(arr)
}


//INPUT
const x = {
    value: 5,
    left: {
        value: 4,
        left: {
            value: 3,
            left: {
                value: 2,
                left: {
                    value: 1,
                    left: {
                        value: 0
                    },
                    right: {
                        value: 1.5
                    }
                },
                right: {
                    value: 2.5
                }
            },
            right: {
                value: 3.5
            }
        },
        right: {
            value: 4.5,
            right: {
                value: 4.8
            }
        }
    },
    right: {
        value: 8,
        left: {
            value: 7
        }
    }
}

getPaths(x);

//OUTPUT

[ '5->4->3->2->1->0',
  '5->4->3->2->1->1.5',
  '5->4->3->2->2.5',
  '5->4->3->3.5',
  '5->4->4.5->4.8',
  '5->8->7' ]

Upvotes: 1

Krishna Majgaonkar
Krishna Majgaonkar

Reputation: 1726

This is my solution for storing all path values in List and then just print the list

Basically what code is recursively calling rootToLeafPaths method and passing the string on values separated by comma (","). The base condition for recursive function is when we reach leaf node (both children are null). At that time, we are just extracting int values from string and storing it in List

class Solution {
    public void printBTfromRootToLeaf (TreeNode root) {
        if(root == null) return 0;
        if (root.left == null & root.right == null) return 1;
        List<List<Integer>> res = new ArrayList();
        rootToLeafPaths(root, res, "");
        System.out.println(res);
    }
private void rootToLeafPaths(TreeNode root, List<List<Integer>> res, String curr) {
        if (root.left == null && root.right == null) {
            String[] vals = curr.split(",");
            List<Integer> temp = new ArrayList<>();
            for (String val : vals) temp.add(Integer.parseInt(val));
            temp.add(root.val);
            res.add(new ArrayList<>(temp));
        }
        if (root.left != null) rootToLeafPaths(root.left, res, curr + root.val + ",");
        if (root.right != null) rootToLeafPaths(root.right, res, curr + root.val + ",");
    }
}

Upvotes: 0

Abhay
Abhay

Reputation: 139

Here is my solution: Once we traverse the left or right path just remove the last element.

Code:

public static void printPath(TreeNode root, ArrayList list) {

    if(root==null)
        return;

    list.add(root.data);

    if(root.left==null && root.right==null) {
        System.out.println(list);
        return;
    }
    else {
        printPath(root.left,list);
        list.remove(list.size()-1);

        printPath(root.right,list);
        list.remove(list.size()-1);

    }
}

Upvotes: 1

lolo
lolo

Reputation: 17864

You can do the following, 

public static void printTreePaths(Node<Integer> node) {
    int treeHeight = treeHeight(node);
    int[] path = new int[treeHeight];
    printTreePathsRec(node, path, 0);

}

private static void printTreePathsRec(Node<Integer> node, int[] path, int pathSize) {
    if (node == null) {
        return;
    }

    path[pathSize++] = node.data;

    if (node.left == null & node.right == null) {
        for (int j = 0; j < pathSize; j++ ) {
            System.out.print(path[j] + " ");
        }
        System.out.println();
    }

     printTreePathsRec(node.left, path, pathSize);
     printTreePathsRec(node.right, path, pathSize);
}

public static int treeHeight(Node<Integer> root) {
    if (root == null) {
        return 0;
    }

    if (root.left != null) {
        treeHeight(root.left);
    }

    if (root.right != null) {
        treeHeight(root.right);
    }

    return Math.max(treeHeight(root.left), treeHeight(root.right)) + 1;

}

Upvotes: 0

neeranzan
neeranzan

Reputation: 131

We can use recursion to achieve it. Right data structure makes it concise and efficient. 

List<LinkedList<Tree>> printPath(Tree root){

    if(root==null)return null;

    List<LinkedList<Tree>> leftPath= printPath(root.left);
    List<LinkedList<Tree>> rightPath= printPath(root.right);

    for(LinkedList<Tree> t: leftPath){
         t.addFirst(root);
    }
    for(LinkedList<Tree> t: rightPath){
         t.addFirst(root);
    }


 leftPath.addAll(rightPath);

 return leftPath;


}

Upvotes: 0

Arif Nadeem
Arif Nadeem

Reputation: 8604

I tried this problem with an ArrayList and my program printed similar paths.

So I modified my logic to work correctly by maintaining an internal count, here is how I did it.

private void printPaths(BinaryNode node, List<Integer> paths, int endIndex) {
        if (node == null)
            return;
        paths.add(endIndex, node.data);
        endIndex++;
        if (node.left == null && node.right == null) {
            //found the leaf node, print this path
            printPathList(paths, endIndex);
        } else {
            printPaths(node.left, paths, endIndex);
            printPaths(node.right, paths, endIndex);
        }
    }

public void printPaths() {
    List<Integer> paths = new ArrayList<>();
    printPaths(root, paths, 0);
}

Upvotes: 0

craftsmannadeem
craftsmannadeem

Reputation: 2933

Here is the correct Implementation 

public static <T extends Comparable<? super T>> List<List<T>> printAllPaths(BinaryTreeNode<T> node) {
    List <List<T>> paths = new ArrayList<List<T>>();
    doPrintAllPaths(node, paths, new ArrayList<T>());
    return paths;
}

private static <T extends Comparable<? super T>> void doPrintAllPaths(BinaryTreeNode<T> node, List<List<T>> allPaths, List<T> path) {
    if (node == null) {
        return ;
    }
    path.add(node.getData());
    if (node.isLeafNode()) {
        allPaths.add(new ArrayList<T>(path));   

    } else {
        doPrintAllPaths(node.getLeft(), allPaths, path);
        doPrintAllPaths(node.getRight(), allPaths, path);
    }
    path.remove(node.getData());
}

Here is the test case

@Test
public void printAllPaths() {
    BinaryTreeNode<Integer> bt = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,6,1,7,3}, new Integer[]{4,6,5,2,7,3,1});
    List <List<Integer>> paths = BinaryTreeUtil.printAllPaths(bt);

    assertThat(paths.get(0).toArray(new Integer[0]), equalTo(new Integer[]{1, 2, 4}));
    assertThat(paths.get(1).toArray(new Integer[0]), equalTo(new Integer[]{1, 2, 5, 6}));
    assertThat(paths.get(2).toArray(new Integer[0]), equalTo(new Integer[]{1, 3, 7}));

    for (List<Integer> list : paths) {          
        for (Integer integer : list) {
            System.out.print(String.format(" %d", integer));
        }
        System.out.println();
    }
}

Here is the output 

1 2 4

1 2 5 6

1 3 7

Upvotes: 3

inyee
inyee

Reputation: 445

/* Given a binary tree, print out all of its root-to-leaf
   paths, one per line. Uses a recursive helper to do the work.*/
void printPaths(Node node) 
{
    int path[] = new int[1000];
    printPathsRecur(node, path, 0);
}

/* Recursive helper function -- given a node, and an array containing
   the path from the root node up to but not including this node,
   print out all the root-leaf paths. */
void printPathsRecur(Node node, int path[], int pathLen) 
{
    if (node == null)
        return;

    /* append this node to the path array */
    path[pathLen] = node.data;
    pathLen++;

    /* it's a leaf, so print the path that led to here */
    if (node.left == null && node.right == null)
        printArray(path, pathLen);
    else
        { 
        /* otherwise try both subtrees */
        printPathsRecur(node.left, path, pathLen);
        printPathsRecur(node.right, path, pathLen);
    }
}

/* Utility that prints out an array on a line */
void printArray(int ints[], int len) 
{
    int i;
    for (i = 0; i < len; i++) 
        System.out.print(ints[i] + " ");
    System.out.println("");
}

Upvotes: 0

Ankur Lathiya
Ankur Lathiya

Reputation: 174

you can do this way also. here is my Java code.

public void printPaths(Node r,ArrayList arr)
{
    if(r==null)
    {
        return;
    }
    arr.add(r.data);
    if(r.left==null && r.right==null)
    {
        printlnArray(arr);
    }
    else
    {
        printPaths(r.left,arr);
        printPaths(r.right,arr);
    }

     arr.remove(arr.size()-1);
}

Upvotes: 4

Filip Vondr&#225;šek
Filip Vondr&#225;šek

Reputation: 1208

Call the recursive methods with:

printAllRootToLeafPaths(node.left, new ArrayList(path));
printAllRootToLeafPaths(node.right, new ArrayList(path));

What happens there when you pass the path (instead of new ArrayList(path) is that you use a single object in all methods call, which means that, when you return to the original caller, the object is not in the same state as it was.

You just need to create a new object and initialize it to the original values. This way the original object does not get modified.

Upvotes: 29

Jeevan
Jeevan

Reputation: 101

public void PrintAllPossiblePath(Node node,List<Node> nodelist)
{
    if(node != null)
    {
            nodelist.add(node);
            if(node.left != null)
            {
                PrintAllPossiblePath(node.left,nodelist);
            }
            if(node.right != null)
            {
                PrintAllPossiblePath(node.right,nodelist);
            }
            else if(node.left == null && node.right == null)
            {

            for(int i=0;i<nodelist.size();i++)
            {
                System.out.print(nodelist.get(i)._Value);
            }
            System.out.println();
            }
            nodelist.remove(node);
    }
}

nodelist.remove(node) is the key, it removes the element once it prints the respective path

Upvotes: 10

akaIDIOT
akaIDIOT

Reputation: 9231

You're passing your list along recursively, but that is a mutable object, so all the calls will modify it (by calling List.add) and mangle your results. Try cloning / copying the path argument to all the recursive calls to provide each branch (harhar) with its own context.

Upvotes: 9

Related Questions