reset password
Author Message
ceejay562
Posts: 25
Posted 21:28 Nov 21, 2014 |

"Write a program that finds the sum of each of the distinct paths from root to (but not including) null in a binary search tree. (Assume the keys are numbers.)" 

Are you asking to find the path from the root to a null with one child/ 2 child nodes that are null?

mnava18
Posts: 86
Posted 22:16 Nov 21, 2014 |

yeah its not very clear what were trying to accomplish.

rabbott
Posts: 1649
Posted 22:29 Nov 21, 2014 |

Find every distinct path from the root to a null and find the sum of the elements in the nodes on those paths. Construct a tree for which you find this unclear, and I'll clarify.

Here's one example. 

The paths to be counted are

[8, 3, 1],  // Terminates because it has two null children; sum = 12

[8, 3, 6, 4], // Terminates because it has two null children; sum = 21

[8, 3, 6, 7], // Terminates because it has two null children; sum = 24

[8, 10], // Terminates because it has one null child; sum = 18

[8, 10, 14, 13],  // Terminates because it has two null children; sum = 45

[8, 10, 14] // Terminates because it has one null child; sum = 32

 

Last edited by rabbott at 10:32 Nov 23, 2014.
ceejay562
Posts: 25
Posted 09:38 Nov 22, 2014 |

Ok thank you. On the wiki page it says the assignment is due tomorrow at might night, but csns says it is due tonight at midnight. Which one is the correct due time?

rabbott
Posts: 1649
Posted 09:43 Nov 22, 2014 |

Sunday, midnight.  The CSNS due date has been changed.

Last edited by rabbott at 09:43 Nov 22, 2014.
G190852562
Posts: 162
Posted 02:09 Nov 23, 2014 |

For the sum of the paths do we add the last node. 

For example the path [8,3,1]  sum = 12  or sum =11

 

 

rabbott
Posts: 1649
Posted 10:29 Nov 23, 2014 |

Include all nodes -- the last one as well. For the path [8, 3, 1] the sum is 12.  See graph post above. I've added the sums.

Last edited by rabbott at 10:32 Nov 23, 2014.