E.g: AllPathsForASum, CountPathsForSum.
Implementation: BinaryTreePathSum
Since we need to find a path from root to leaf, our check condition is:
O(n), in the worst case, we look through all nodes.
O(n), for the recursion stack in the worst case.
The worst case here would be a tree that looks like a LinkedList.
Implementation: AllPathsForASum
Pretty much same as above, except we need to backtrack after computing a path. Why?
Consider we went down 1 -> 9 -> 2. As we bubble up, we are going to go through the right sub-tree (1 -> 9 -> 7). In that case, it doesn't make sense to keep 2 in the path because that path will never contain 2. Hence, as we bubble up, we remove the last element seen.
O(n^2), the typical DFS takes O(n). However, for every path found, we copy and store that path, which could cost O(n*n) or O(n^2).
O(n) for the recursion stack. For the list to store the paths, there can only be as many paths as the number of leaf nodes, which is N+1/2. Thus, at most we need O(n) space. If this was a LinkedList, there would be N nodes to store, making the space complexity O(n^2). However, if it were a balanced binary tree, the depth would be O(logn). Thus, the space complexity would be O(nlogn).
Implementation: AllRootToLeafNodes
Similar to the one above.
Implementation: SumOfPathNumbers
So, first of all, we need to find the individual numbers. Once we have a list of the individual numbers, its trivial to calculate the sum of them.
To find the individual numbers, we find all paths from root to leaf and calculate the number on the fly. The formula is:
number = (number*10) + node.value
where number starts from 0
O(n), we go through the tree nodes exactly once and we do not store an array of nodes.
O(logn), in the worst case for a balanced BT, we need logn space (one path per leaf node) to store all the numbers. However, we need O(n) space for the recursion stack. So total space complexity is O(n+logn) = O(n).
Implementation: PathWithGivenSequence
As we go down the path from root to leaf, we need to keep track of the index in the sequence that we are comparing against. If any comparison fails, we return false and that path is invalid. If any of the paths turns out valid, we return true, else false.
A path turns out to be valid if the leaf is equal to the last number in the sequence.
O(n), traverses every node.
O(n), for the recursion stack.
Implementation: CountPathsForSum
As we go down the tree figuring out paths, we need to look back up and see if any subpath makes the sum. If so, we got another path to consider.
As always if we go down a path that doesnt work out for us, we need to backtrack and go down a different path.
O(n^2)
O(n)
Implementation: TreeDiameter
This problem follows the Binary Tree Path Sum pattern. We can follow the same DFS approach. There will be a few differences:
diameter = leftTreeHeight + rightTreeHeight + 1. To find the overall tree diameter, we will use a class level variable. This variable will store the maximum diameter of all the nodes visited so far, hence, eventually, it will have the final tree diameter.We are basically calculating the height of the tree, so time complexity is O(n).
O(n), for the recursion stack.
Implementation: PathWithMaxSum
Similar to calculating the diameter, but instead we calculate the sum and choose a path with the max sum.
O(n)
O(n)