# Theory

## Why we might need to backtrack

E.g: AllPathsForASum, CountPathsForSum.

# Questions

## Given a binary tree and a number ‘S’, find if the tree has a path from root-to-leaf such that the sum of all the node values of that path equals ‘S’.

Implementation: BinaryTreePathSum

Since we need to find a path from root to leaf, our check condition is:

1. If its a leaf and the sum of that path is target, we return true.
2. If any of the paths is true, we return true.
3. If its a leaf node and the path sum is not equal to target, we return false.

### Time complexity

`O(n)`, in the worst case, we look through all nodes.

### Space complexity

`O(n)`, for the recursion stack in the worst case.

The worst case here would be a tree that looks like a LinkedList.

## Given a binary tree and a number ‘S’, find all paths from root-to-leaf such that the sum of all the node values of each path equals ‘S’.

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.

### Time complexity

`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)`.

### Space complexity

`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)`.

## Given a binary tree, return all root-to-leaf paths.

Implementation: AllRootToLeafNodes

Similar to the one above.

## Given a binary tree where each node can only have a digit (0-9) value, each root-to-leaf path will represent a number. Find the total sum of all the numbers represented by all paths.

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
``````

### Time complexity

`O(n)`, we go through the tree nodes exactly once and we do not store an array of nodes.

### Space complexity

`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)`.

## Given a binary tree and a number sequence, find if the sequence is present as a root-to-leaf path in the given tree.

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.

### Time complexity

`O(n)`, traverses every node.

### Space complexity

`O(n)`, for the recursion stack.

## Given a binary tree and a number ‘S’, find all paths in the tree such that the sum of all the node values of each path equals ‘S’. Please note that the paths can start or end at any node but all paths must follow direction from parent to child (top to bottom).

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)`

## Given a binary tree, find the length of its diameter. The diameter of a tree is the number of nodes on the longest path between any two leaf nodes. The diameter of a tree may or may not pass through the root. Note: You can always assume that there are at least two leaf nodes in the given tree.

Implementation: TreeDiameter

This problem follows the Binary Tree Path Sum pattern. We can follow the same DFS approach. There will be a few differences:

1. At every step, we need to find the height of both children of the current node. For this, we will make two recursive calls similar to DFS.
2. The height of the current node will be equal to the maximum of the heights of its left or right children, plus ‘1’ for the current node.
3. The tree diameter at the current node will be equal to the height of the left child plus the height of the right child plus ‘1’ for the current node: `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.

### Time complexity

We are basically calculating the height of the tree, so time complexity is `O(n)`.

### Space complexity

`O(n)`, for the recursion stack.

## Find the path with the maximum sum in a given binary tree. Write a function that returns the maximum sum. A path can be defined as a sequence of nodes between any two nodes and doesn’t necessarily pass through the root. The path must contain at least one node.

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)`