Identify

Motive

use recursion (or a stack for the iterative approach) to keep track of all the previous (parent) nodes while traversing
works by starting at the root of the tree, if the node is not a leaf you need to do three things:
- decide whether to process the current node now (pre-order),
  
  or between processing two children (in-order)
  
  or after processing both children (post-order)
- make two recursive calls for both the children of the current node to process them.

We will be using recursion (or we can also use a Stack for the iterative approach) to keep track of all the previous (parent) nodes while traversing. This also means that the space complexity of the algorithm will be O(h), where h is the maximum height of the tree.
To recursively traverse a binary tree in a DFS fashion, we can start from the root and at every step, make two recursive calls one for the root.left and one for the root.right child by subtracting the value of the current node from the given number: sum - root.val.

O(n) recursion stack, the worst case will happen when the given tree is a linked list