Tree Depth First Search

Question 1

112. Path Sum

Problem Statement

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.

Example:
Given the below binary tree and sum = 22,
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

TC – O(n)
SC – O(n)

Answer 1

Takeaways:
1. First check for negative condition . i.e if root==null return false and then for positive condition i.e if its leaf node and sum so far is equal to desired sum.

Pseudo code:
1. Start DFS with the root of the tree.
2. If the current node is not a leaf node, do two things:
o Subtract the value of the current node from the given number to get a new sum => S = S - node.value
o Make two recursive calls for both the children of the current node with the new number calculated in the previous step.
3. At every step, see if the current node being visited is a leaf node and if its value is equal to the given number ‘S’. If both these conditions are true, we have found the required root-to-leaf path, therefore return true.
4. If the current node is a leaf but its value is not equal to the given number ‘S’, return false.