Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Introduction to Tree Depth First Search Pattern

You are given a binary tree and a target sum S. Decide whether a path from the root to a leaf adds up to S.

        12
      /    \
     7      1        S = 23
    /      / \
   4      10  5

12 -> 1 -> 10 = 23

This question is about one complete route through the tree.

Level Order Traversal visits every node at one depth before moving deeper. That order is not helpful for following one path.

Depth First Search (DFS) follows one branch as far as possible. It then returns to an earlier node and tries another branch.

.....

.....

.....

Like the course? Get enrolled and start learning!
Pradeep R

Pradeep R

· 11 days ago

DFS tree chapter has relatively few questions. It would have been helpful to include more problems demonstrating when to use preorder, inorder, and postorder traversal.

Show 1 reply
Faraz Ahmed

Faraz Ahmed

· 6 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 2 replies

Reading Progress

0%

Vote for new content