DFS Complexity with two recursive calls to each child in binary tree

Question

So let's say the problem is calculating the number of paths in a binary tree whose sum is equal to some target.

One simple way to do this is to recursively call DFS twice for each child, once for using child node for a path that started somewhere before it and once to start searching for path starting at child node.

Time complexity of this approach would be O(4^k), where k is the height of the tree, but what would be the complexity in respect to the number of nodes n in the tree?

I know that regular DFS has O(n) time complexity since it visits each tree node only once, but this approach would visit node at level m 2^m times if I'm not mistaken.

Here is my code for the problem in python.

def cnt_paths(root, target):
    return dfs(root, target, 0, set())


def dfs(node, target, current_sum, visited):
    cnt = 0
    if current_sum + node.val == target:
        cnt += 1

    if node.left:
        cnt += dfs(node.left, target, current_sum + node.val, visited)  # include this node
        if node.left not in visited:
            cnt += dfs(node.left, target, 0, visited)  # start from scratch on next node
            visited.add(node.left)

    if node.right:
        cnt += dfs(node.right, target, current_sum + node.val, visited)
        if node.right not in visited:
            cnt += dfs(node.right, target, 0, visited)
            visited.add(node.right)

    return cnt

Berthur · Accepted Answer · 2021-03-12 12:43:44Z

0

Without looking any deeper into your code, if indeed you already know that its time complexity is O(4^k) for tree height k, then we can find the complexity for the number of nodes too.

A binary tree of height k has n = O(2^k) nodes, Thus,

O(4^k) = O(4^log₂(n)) = O(2^{2 * log₂(n)}) = O((2^log₂(n))²)= O(n²).

edited Mar 12, 2021 at 12:43

answered Mar 12, 2021 at 12:37

Berthur

4,5142 gold badges20 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

trincot · Accepted Answer · 2021-03-12 15:07:56Z

The complexity you list is not correct. If the depth of a node is d, then that node is used together with d different starting points of the sum (the root, the root's child, ... the node's parent, or the node itself). In other words, the expression current_sum + node.val is evaluated d times for a particular node (but with varying current_sum values).

This means in total you have SUM[depth(node)] of such operations. In a perfect binary tree, this sum is:

1 + 2*2 + 3*4 + 4*8 + ... + 𝑘2^𝑘-1

where 𝑘 is the height of the tree. This sum is smaller than

𝑘 ∑_{_𝑖=1..𝑘}2^𝑖-1

which equals 𝑘(2^𝑘-1), which is

O(𝑘2^𝑘)

The number of nodes 𝑛 in a perfect binary tree of height 𝑘 is 𝑛=2^𝑘, so the number of operations, rewritten in terms of 𝑛 is:

O(𝑛log(𝑛))

Collectives™ on Stack Overflow

DFS Complexity with two recursive calls to each child in binary tree

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related