time complexity of Print all nodes from root to leaves

Question

I have using DFS and recursive to code this problem, shows below:

/**
 * recursive
 */
public static List<List<Integer>> printAllPath(TreeNode root) {
    List<List<Integer>> rst = new ArrayList<List<Integer>>();

    helper(rst, new ArrayList<Integer>(), root);
    return rst;
}

public static void helper(List<List<Integer>> rst, ArrayList<Integer> list,
                   TreeNode root) {
    if (root == null) {
        return;
    }
    list.add(root.val);
    if (root.left == null && root.right == null) {
        rst.add(new ArrayList<Integer>(list));
    }
    helper(rst, list, root.left);
    helper(rst, list, root.right);
    list.remove(list.size() - 1);
}

And after search for the internet, I found that the average time complexity of this algorithm is O(nlogn), and the worse case is O(n^2), is this right? and WHY? Can anyone kindly explain it?

I am not very familiar with analysis the time complexity of tree. In this problem, if I am using Queue to implement, the time complexity should be O(n) right? because I just iterate the whole tree once.

But how to analysis the time complexity of a tree that using recursive.?

@TimBiegeleisen I don't know how to analysis the time complexity of this algorithm — Jie, Mar 26 '15 at 07:08
Don't know what you are trying to do, but since you will touch each node in the tree once the running time should be `O(n)`. — Tim Biegeleisen, Mar 26 '15 at 07:09

Miljen Mikic · Accepted Answer · 2017-07-31T11:45:27.367

Your code obviously collects and returns all paths from the root to the leaf nodes. It does so by using DFS. Every node is visited during the algorithm execution, and none of them is visited more than once. However, you have to either print or store the path when you find it. In your program, you create new ArrayList and store it in variable rst. Number of paths equals the number of leaf nodes l, and the path length equals the height of the tree h, so the total complexity is O(n + hl).

Values of l and h are not independent, so let us examine two interesting cases. In case of balanced binary tree, there are n/2 leaf nodes on average, and height is log2(n), which gives O(nlogn). On the other hand, when tree degenerates in the linked list, there is only one leaf and the length of that path is n, so the complexity for this case is O(n).

But how to analysis the time complexity of a tree that using recursive?

Regarding the time complexity, just count the number of recursive calls. If the space complexity is an issue, replace the recursion by iteration.

See also:

DFS and BFS complexity

Don't you think the code "rst.add(new ArrayList(list));" contributes to extra complexity? For all leaf nodes we do this. O((2^(l-1)) * O(logn)) — unknown_boundaries, Jul 30 '17 at 00:36
Hi, in your opinion, what is the **worst case** of h*l? O(nlogn)? — ryh, Sep 04 '20 at 06:37

score 1 · Answer 2 · answered Apr 20 '17 at 04:41

When building a root-to-leaf path every node in the tree is touched once, so it's O(N) complexity, where N is amount of nodes in the tree, as mentioned above.

But when root-to-leaf path is added to the list of results (rst.add(new ArrayList<Integer>(list)); in your snippet), then whole array that contains the path is copied. Since complexity of array copy is linear to its length and array representing root-to-leaf path contains, roughly, h nodes, where h is height of the tree, than it's O(N * h) overall complexity.

For example, consider perfect binary tree. It has N / 2 leaf nodes, and, hence, N / 2 root-to-leaf paths of log N length each. Iterating over each of these paths -- for straightforward copy or print -- involves, in total, exactly log N * N / 2, which is equivalent to O(N * h).

time complexity of Print all nodes from root to leaves

2 Answers2

Linked