find all paths from root to leaf of a binary tree

Question

I write a recursive algorithm to find all the paths of a binary tree. Basically, you will find the leftmost path, put the nodes in a stack and gradually find the right branches. As far as I tested, the algorithm works fine but added a null entry during the recursion.

For example, the tree an example tree is provided below,

               4
              /  \
             5    6
            /    / \
           4    1   6
          / \
         5  12
             \
             13

The code should provides the paths:

[4, 5, 4, 5]
[4, 5, 4, 12, 13]
[4, 6, 1]
[4, 6, 6]

The Node definition is here,

private static class Node {

        public int key;

        public Node left;
        public Node right;

        public Node(int key) {
            this.key = key;
        }
    }

The algorithm to find all the paths provided below,

/*
 * find all the paths of a binary search tree
 * */
private static void findPaths(Node node, List<List<Integer>> lists, Stack<Node> stack) {

    if (node == null) {
        return;
    }

    List<Integer> list = null;

    stack.push(node);

    while (node.left != null) {
        node = node.left;
        stack.push(node);
    }

    /////////
    if (stack.peek().right != null) {
        findPaths(stack.peek().right, lists, stack);
    }
    /////////


    if (stack.size() > 0) {
        list = new ArrayList<>();
    }

    for (Node n : stack) {
        list.add(n.key);
    }

    lists.add(list);

    Node right = null;

    /*
     * i.    pop till the stack has elements
     * ii.   delete the old left paths that are already included
     * iii.  delete the old right path that are already included
     *
     * */
    while (stack.size() >0 && (stack.peek().right == null || stack.peek().right.equals(right))) {
        right = stack.pop();
    }


    /*
     * for the right paths
     * */
    if (stack.size() == 0) {
        return;
    }

    right = stack.peek().right;

    findPaths(right, lists, stack);
}

I debug the issue and find that when I reached the end of computation,

       if (stack.size() == 0) {
            return;
        }

the code hits return and then without ending all the works for the method, it still plays inside and goes here,

if (stack.size() > 0) {
        list = new ArrayList<>();
    }

    for (Node n : stack) {
        list.add(n.key);
    }

    lists.add(list);

Obviously, it can't do much afterward and finally leaves the method.

I would appreciate if anyone can help me to improve the code. I assume it comes from using the 2 return statement. Is it allowed in Java and if so, what will be the walk-through for the situation?

Answer 1

I have a recursive solution that can provide all the paths from the root to the leaf of a binary tree. The solution is provided below,

public static List<List<Node>> findAllPaths(List<List<Node>> paths, Node node, List<Node> path) {

        if (node == null) {
            return paths;
        }

        path.add(node);

        if (node.left == null && node.right == null) {

            paths.add(path);
            return paths;
        }

        //
        else {
            findAllPaths(paths, node.left, new ArrayList<>(path));
            findAllPaths(paths, node.right, new ArrayList<>(path));
        }

        return paths;
    }

Answer 2

Well C++ is not that different than Java in terms of such codes. Below is the C++ implementation of the problem specified above.

vector< vector< int > > ans;

void solution(TreeNode *root, vector<int> &current){
    if(root == NULL)
        return;
    current.push_back(root->val);
    if(root->left == NULL and root->right == NULL)
        ans.push_back(current);

    if(root->left)
        solution(root->left, current);

    if(root->right)
        solution(root->right, current);

    current.pop_back();
} 


vector<vector<int> > Solution::pathSum(TreeNode* A) {
    ans.clear();
    vector<int> current;
    solution(A, current);
    return ans;
}

The above approach uses the recursion and maintains the path. Whenever we hit the solution i.e the leaf, we consider that a solution and pop that element to search for other solution moving down the tree.

Answer 3

As mentioned in the comments, you don't need a separate stack. You can make use of recursive call and return paths from child nodes and add parent node to each path available.

private static List<List<Integer>> findPaths(Node node){

    if (node == null) 
        return new ArrayList<List<Integer>>();

    List<List<Integer>> paths = new ArrayList<List<Integer>>();

    List<List<Integer>> left_subtree = findPaths(node.left);
    List<List<Integer>> right_subtree = findPaths(node.right);


    for(int i=0;i<left_subtree.size();++i){
        List<Integer> new_path = new ArrayList<Integer>();
        new_path.add(node.key);
        new_path.addAll(left_subtree.get(i));
        paths.add(new_path);
    }

    for(int i=0;i<right_subtree.size();++i){
        List<Integer> new_path = new ArrayList<Integer>();
        new_path.add(node.key);
        new_path.addAll(right_subtree.get(i));
        paths.add(new_path);
    }


    if(paths.size() == 0){
        paths.add(new ArrayList<Integer>());
        paths.get(0).add(node.key);
    }

    return paths;
}