Difference Between Sum of Nodes at Odd Levels and Sum of Nodes at Even Levels of a Binary Tree Using Recursion

Approach 

Recursively substract the data values of child nodes from current node.

Assume the full and complete tree with levels as:

6

11

1111

This will become 6 - (1-1-1) - (1-1-1) => 6 - (-1) - (-1) => 6+1 + 1 => 8.

 

Solution

int getLevelDiff(TreeNode n)
{
  if(n==null) return 0;
  
  return (n.data - getLevelDiff(n.left) - getLevelDiff(n.right));
}

 

Complexity

Time complexity will be O(n)

Space complexity will be O(log n) for recursive calls.

 

Solution for a non-binary tree

If we need to apply this for a generic tree (non-binary tree), we can do it as below assuming getChildren return a collection of trees that implements the Iterator interface:

int getLevelDiff(TreeNode n)
{
  if(n==null) return 0;
  
  int diffSum  = n.data;

  for(TreeNode t: n.getChildren())
  {
    diffSum = diffSum - getLevelDiff(t);
  }
  
  return diffSum;
}

Complexities will be similar to that of the original solution.

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)