Check if a Binary Tree is Balanced in O(N) time complexity

Problem statement

Check if a Binary Tree is Balanced in O(N) time complexity.

Assumption: Heights of two subtrees of any node should never differ by more than one, to consider a tree as balanced.

 

Approach

We can use a recursive function that will return the height of its subtree, or a special integer (-1) if the node is not balanced.

In every recusrive call, 

if node is null, then return 0.

if any subtree return -1 or difference of height of left and right subtree is more than 1, then return -1.

if all is well, return the max height (out left and right tree) + 1.

 

Solution

int checkHeight(TreeNode n)

{

  if( n == null ) return 0;

 

  int leftHeight = checkHeight( n.left );

  if (leftHeight == -1) return -1;

 

  int rightHeight = checkHeight( n.right );

  if (rightHeight == -1) return -1;

 

  if (Math.absolute ( leftHeight - rightHeight ) > 1 ) return -1;

 

  return Math.max ( leftHeight, rightHeight) + 1;

 

}

 

Complexities

Time complexity is O(N)

Space complexity is O( log N) 

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)