Grokking 75: Top Coding Interview Questions
Vote

0% completed

​

Introduction to Tree Depth First Search Pattern

You are given a binary tree and a number S. Decide whether any path from the root down to a leaf has values that add up to S.

        12
      /    \
     7      1        S = 23, and 12 -> 1 -> 10 adds up to it
    /      / \
   4      10  5

A queue is no help here. Breadth First Search visits nodes level by level, so it never holds a complete root to leaf path at any moment. This question is about paths, and a path is a branch followed to its end.

Depth First Search does exactly that. Go down one branch as far as it goes, then come back up and take the next one

.....

.....

.....

Like the course? Get enrolled and start learning!
Faraz Ahmed

Faraz Ahmed

· 5 months ago

why return Max Integer for base case, if there is no right or left for a current node, cant we return 0?

lets take this example: 3 / 1

here for 3 the left is 1 and right is 0 , the minimum for left subtree and right subtree of 3 will not be 3 itself??

leftSum = 1 right Sum = 0

sum for this node: 3 + Min(1,0) = 3

Show 1 reply