print all root to leaf paths in a binary tree

Question

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...

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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);
}

Answer 5

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

Answer 6

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);

    }
}

Answer 7

/* 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("");
}

Answer 8

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);
}

Answer 9

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;


}

Answer 10

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;

}

Answer 11

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 + ",");
    }
}

Answer 12

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' ]