Find All Paths Whose Sum of Data nodes will be Equal to a Given Value

Problem

Given a binary tree with an integer data element; find all paths whose sum of data nodes will be equal to a given value.

Path can start or end anywhere in the tree.

Example: If the sum given is 5 and a  path is 2->3->1>-1. There you should print two paths here: 2->3 and 2->3->1>-1.

 

Approach

Initial thoughts might be to go from every node and see if the path sums to the given value and print it. However you will still needs to go till the end to take care of the second path above.

A better cleaner solution will be to have a path array also passed along.

From every level, we will see if any path till that element gives the sum and print them.

To pass along the path, we need to assume that we know the depth as we need to create the path array with a size equal to depth.

 

Solution

void findPath(TreeNode n, int sum, int[] path, int level)

{

  path[level] = n.data;

  int s = 0;

  for(int i = level; i>=0; i--)

  {

    s = s + path[i];

    if( s == sum) print (path, i , level);

  }

 

  findPath(n.left, sum, path, level+1);

  findPath(n.right, sum, path, level + 1);

}

print (path, i , level) will print the elements of path array from location i to level.

this method can be invoked as:

int[] path = new int[depth];

findPath(root, sum, path, 0);

 

Complexity

Time and space complexity will be O(n logn).

Quick Notes Finder Tags

Activities (1) advanced java (1) agile (3) App Servers (6) archived notes (2) ArrayLists (1) Arrays (2) Best Practices (12) Best Practices (Design) (3) Best Practices (Java) (7) Best Practices (Java EE) (1) BigData (3) Chars & Encodings (6) coding problems (2) Collections (15) contests (3) Core Java (All) (53) course plan (2) Database (12) Design patterns (8) dev tools (3) downloads (2) eclipse (9) Essentials (1) examples (14) Exception (1) Exceptions (4) Exercise (1) exercises (6) Getting Started (18) Groovy (2) hadoop (4) hibernate (77) hibernate interview questions (6) History (1) Hot book (4) http monitoring (2) Inheritance (4) intellij (1) java 8 notes (4) Java 9 (1) Java Concepts (7) Java Core (7) java ee exercises (1) java ee interview questions (2) Java Elements (16) Java Environment (1) Java Features (4) java interview points (4) java interview questions (4) javajee initiatives (1) javajee thoughts (3) Java Performance (6) Java Programmer 1 (11) Java Programmer 2 (8) Javascript Frameworks (1) Java SE Professional (1) JSP (1) Legacy Java (1) linked list (3) maven (1) Multithreading (16) NFR (1) No SQL (1) Object Oriented (9) OCPJP (4) OCPWCD (1) OOAD (3) Operators (4) Overloading (2) Overriding (2) Overviews (1) policies (1) programming (1) Quartz Scheduler (1) Quizzes (17) RabbitMQ (1) references (2) resources (1) restful web service (3) Searching (1) security (10) Servlets (8) Servlets and JSP (31) Site Usage Guidelines (1) Sorting (1) source code management (1) spring (4) spring boot (3) Spring Examples (1) Spring Features (1) spring jpa (1) Stack (1) Streams & IO (3) Strings (11) SW Developer Tools (2) testing (1) troubleshooting (1) user interface (1) vxml (8) web services (1) Web Technologies (1) Web Technology Books (1) youtube (1)