codebytes: An algorithm to print all paths which sum to a given value in a Binary Tree.
An algorithm to print all paths which sum to a given value in a Binary Tree.
Q. You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path does not need to start or end at the root or a leaf.
Algorithm:
1. Start at the root or any other node (if a node other than root is given).
2. Check all nodes to left and to right recursively, pass the running sum and a string representation of the path downwards.
3. If the sum equals the required value, store that path or print it.
4. Continue down until you hit a null. (We don't quit when running sum matches the required value as there may be negative value nodes down in the path and then a positive one or there maybe zero value nodes down in the tree which IS a possible path).
Algorithm:
1. Start at the root or any other node (if a node other than root is given).
2. Check all nodes to left and to right recursively, pass the running sum and a string representation of the path downwards.
3. If the sum equals the required value, store that path or print it.
4. Continue down until you hit a null. (We don't quit when running sum matches the required value as there may be negative value nodes down in the path and then a positive one or there maybe zero value nodes down in the tree which IS a possible path).
Read full article from codebytes: An algorithm to print all paths which sum to a given value in a Binary Tree.
No comments:
Post a Comment