Print all paths from root to leaf in a Binary tree

Question

Here is the code I wrote to print all paths of a Binary tree from root to leaf:

public static void printRootToLeaf(Node1 root, List<Integer> list) {
    if(root == null) {
        return;
    }

    list.add(root.data);

    if(root.left == null && root.right == null) {
        System.out.println(list);
        return;
    }

        printRootToLeaf(root.left, list);
        printRootToLeaf(root.right, list);

}

I am calling this method in main like this:

public static void main(String[] args) {

    Node1 root = new Node1(1);
    Node1 two = new Node1(2);
    Node1 three = new Node1(3);
    Node1 four = new Node1(4);
    Node1 five = new Node1(5);
    Node1 six = new Node1(6);
    Node1 seven = new Node1(7);
    Node1 eight = new Node1(8);

    root.left = two;
    root.right = three;
    two.left = four;
    two.right = five;
    three.left = six;
    three.right = seven;
    five.left = eight;

    printRootToLeaf(root, new ArrayList<Integer>());

}

I get the result:

[1, 2, 4]
[1, 2, 4, 5, 8]
[1, 2, 4, 5, 8, 3, 6]
[1, 2, 4, 5, 8, 3, 6, 7]

while i was expecting:

[1, 2, 4]
[1, 2, 5, 8]
[1, 3, 6]
[1, 3, 7]

What should I fix to make this work? I know this is similar to this, but I am unable to follow that answer. Thanks.

Answer 1

Here is a simpler example.

Node1 root = new Node1(1);
root.left = new Node(2);
root.right = new Node(3);

With the expected result

[1,2]
[1,3]

And actual result

[1,2]
[1,2,3]

When you first call printRootToLeaf, List is empty. You add 1 to it, and call printRootToLeaf on the left branch. Within that call, you add 2 to the list, and print [1,2]. You then return to the first call, but 2 is still in the list! You then call printRootToLeaf on the right branch. Within that call, you add 3 to the list, and print [1,2,3].

Changes made to the list while recursing down the left branch shouldn't propogate to the list passed down the right branch. The easiest way to address this is to make copies of the list each time:

printRootToLeaf(root.left, copy(list));
printRootToLeaf(root.right, copy(list));

The actual method of copying the list will vary depending upon what language you're using.

Answer 2

The problem is that you're not removing elements, so you go down one side of the tree, filling up your list, then you go down the other and the old elements are still there.

Untested code that removes elements:

public static void printRootToLeaf(Node1 root, List<Integer> list) {
    if(root == null) {
        return;
    }

    list.add(root.data);

    if(root.left == null && root.right == null) {
        System.out.println(list);
        // cast so we don't remove by index (would happen if 'data' is an int)
        list.remove((Integer)root.data);
        return;
    }

    printRootToLeaf(root.left, list);
    printRootToLeaf(root.right, list);
    // cast so we don't remove by index  (would happen if 'data' is an int)
    list.remove((Integer)root.data);
}

remove(Object) is not particularly efficient, using LinkedList and then removeLast() might be a good idea.

Answer 3

This is a C# Implementation. You need to create a new List and put the existing path there.

    public static void PrintRoot2Leaves(Node root, List<int> path)
    {
        if (root == null) { return; }
        path.Add(root.Value);
        if (root.Left == null && root.Right == null)
        {
            Console.WriteLine(string.Join(",", path));
            return;
        }
        else {
            PrintRoot2Leaves(root.Left, new List<int>(path));
            PrintRoot2Leaves(root.Right, new List<int>(path));
        }
    }

Answer 4

If you have the reference to parent node, following code can print the paths:

public void printPaths(Node n) {
    if(n != null) {
        if(n.left == null && n.right == null) { // found a leaf node, go up the tree
            StringBuilder sb = new StringBuilder();
            sb.append(" ").append(n);
            Node p = n.parent;
            while(p != null) {
                sb.insert(0, " ").insert(1,p);
                p = p.parent;
            }
            System.out.println(sb);
        }
        printPaths(n.left);
        printPaths(n.right);
    }
}

Answer 5

The question here is how did you get the solution rather than did you get the solution. The performance is the key here. Create a tree object first..

class Node {

public Node left;
public Node right;
public Character val;

public Node(char val) {
    this.val = val;
}   

get all paths in list..

public List<LinkedList<Node>> printPath(Node root) {

    if (root == null) return new ArrayList<LinkedList<Node>>();

    List<LinkedList<Node>> left = printPath(root.left);
    List<LinkedList<Node>> right = printPath(root.right);

    left.addAll(right);

    for (LinkedList<Node> lst : left) {
        lst.addFirst(root);
    }
    if(left.size()==0){
        LinkedList<Node> lst= new LinkedList<Node>();
        lst.add(root);
        left.add(lst);
    }
    return left;

}

print all the paths now..

  Node root = new Node('a');
    System.out.println(root.val);
    root.left = new Node('b');
    root.left.left = new Node('c');
    root.left.right = new Node('d');
    root.right = new Node('e');
    root.right.left = new Node('f');
    root.right.right = new Node('g');
    root.right.right.left = new Node('h');

    List<LinkedList<Node>> allPaths = wc.printPath(root);

    for (LinkedList<Node> lst : allPaths) {
        for (Node node : lst)
            System.out.print(node.val==null ? "-" : node.val);
        System.out.println();
    }