Algorithm cheatsheet

Binary Tree

General steps for DFS:

1. skip condition (start/leaf node)

2. visit current node (add current node to path, add sum etc)

3. DFS left and right

4. clean up (rollback whatever is shared across calls)

---

Find # of paths from root that sum to target

Precondition:

Binary tree with integer nodes. Given root of the tree, find # of paths from root that sum to target.

Algorithm:

Parameters: 
n = current node to be processed
cum=cumulative sum of path from original root to (up to and excluding) n

int count(n, cum):
	if (n == null): return 0
	found = 0
	cum += n.val
	if (cum == target):
		found++
	found += count(n.left, cum)
	found += count(n.right, cum)
	return found

Usage:

result = count(tree_root, 0)

---

Find path from root to target

Precondition: 

Binary tree with integer nodes. Given root, find path from root to that target

Algorithm:

n: root node or currently visiting node
t: target number; same for all calls
path: path to t from root; same reference for all calls
FoundPathException: needed since need to exist out of stacks of recursive calls

void findPath(n, t, path):
	if(n==null) return
	path.add(n)
	if(t == n) throw new FoundPathException()
	DFS(n.left, t, path)
	DFS(n.right, t, path)
	path.removeLast()

Usage: 

path = []

root = getRandomBinaryTree()

target = 5 // find node with '5'

findPath(root, target, path)

print(path)

---

If link to parent is present

Find depth of node

Precondition: binary tree, link to parent is present. 

n: node
count: assume first level is 1, return depth of n

int depth(n):
	int count = 0
	while(n != null):
		count++
		n = n.parent
    return count

Usage:

int depth = depth(n)