How to determine if binary tree is balanced

Question

It s been a while from those school years  Got a job as IT specialist at a hospital   Trying to move to do some actual programming now   I m working on binary trees now  and I was wondering what would be the best way to determine if the tree is height-balanced     I was thinking of something along this   public boolean isBalanced Node root       if root  null           return true     tree is empty           else          int lh   root left height            int rh   root right height            if lh - rh  gt  1    rh - lh  gt  1               return false                      return true      Is this a good implementation  or am I missing something

User · Answer

public int height Node node       if node  null return 0      else          int l height node leftChild           int r height node rightChild          return l gt r l 1 r 1       public boolean balanced Node n        int l  height n leftChild       int r  height n rightChild        System out println l        r       if Math abs l-r  gt 1          return false      else          return true

User · Answer

Note 1  The height of any sub-tree is computed only once   Note 2  If the left sub-tree is unbalanced then the computation of the right sub-tree  potentially containing million elements  is skipped      return height of tree rooted at  tn  if  and only if  it is a balanced subtree    else return -1 int maxHeight  TreeNode const   tn         if  tn             int const lh   maxHeight  tn- gt left            if  lh    -1   return -1          int const rh   maxHeight  tn- gt right            if  rh    -1   return -1          if  abs  lh - rh    gt  1   return -1          return 1   max  lh  rh              return 0     bool isBalanced  TreeNode const   root            Unless the maxHeight is -1  the subtree under  root  is balanced     return maxHeight  root      -1

User · Answer

static boolean isBalanced Node root          check in the depth of left and right subtree     int diff   depth root getLeft    - depth root getRight         if  diff  lt  0            diff   diff   -1            if  diff  gt  1            return false              go to child nodes     else           if  root getLeft      null  amp  amp  root getRight      null                return true            else if  root getLeft      null                if  depth root getRight     gt  1                    return false                else                   return true                          else if  root getRight      null                if  depth root getLeft     gt  1                    return false                else                   return true                          else if  root getLeft      null  amp  amp  root getRight      null  amp  amp  isBalanced root getLeft     amp  amp  isBalanced root getRight                   return true            else               return false

User · Answer

Well  you need a way to determine the heights of left and right  and if left and right are balanced   And I d just return height node- gt left     height node- gt right    As to writing a height function  read  Understanding recursion

User · Answer

What kind of tree are you talking about  There are self-balancing trees out there  Check their algorithms where they determine if they need to reorder the tree in order to maintain balance

User · Answer

RE   lucky s solution using a BFS to do a level-order traversal   We traverse the tree and keep a reference to vars min max-level which describe the minimum level at which a node is a leaf   I believe that the  lucky solution requires a modification  As suggested by  codaddict  rather than checking if a node is a leaf  we must check if EITHER the left or right children is null  not both   Otherwise  the algorithm would consider this a valid balanced tree        1            2   4                3   1   In Python   def is bal root       if root is None          return True      import queue      Q   queue Queue       Q put root       level   0     min level  max level   sys maxsize  sys minsize      while not Q empty            level size   Q qsize            for i in range level size               node   Q get                if not node left or node right                  min level  max level   min min level  level   max max level  level               if node left                  Q put node left              if node right                  Q put node right           level    1          if abs max level - min level   gt  1              return False      return True   This solution should satisfy all the stipulations provided in the initial question  operating in O n  time and O n  space  Memory overflow would be directed to the heap rather than blowing a recursive call-stack   Alternatively  we could initially traverse the tree to compute   cache max heights for each root subtree iteratively  Then in another iterative run  check if the cached heights of the left and right subtrees for each root never differ by more than one  This would also run in O n  time and O n  space but iteratively so as not to cause stack overflow

User · Answer

Stumbled across this old question while searching for something else  I notice that you never did get a complete answer   The way to solve this problem is to start by writing a specification for the function you are trying to write   Specification  A well-formed binary tree is said to be  height-balanced  if  1  it is empty  or  2  its left and right children are height-balanced and the height of the left tree is within 1 of the height of the right tree   Now that you have the specification  the code is trivial to write  Just follow the specification   IsHeightBalanced tree      return  tree is empty  or              IsHeightBalanced tree left  and             IsHeightBalanced tree right  and             abs Height tree left  - Height tree right    lt   1    Translating that into the programming language of your choice should be trivial   Bonus exercise  this naive code sketch traverses the tree far too many times when computing the heights  Can you make it more efficient   Super bonus exercise  suppose the tree is massively unbalanced  Like  a million nodes deep on one side and three deep on the other  Is there a scenario in which this algorithm blows the stack  Can you fix the implementation so that it never blows the stack  even when given a massively unbalanced tree   UPDATE  Donal Fellows points out in his answer that there are different definitions of  balanced  that one could choose  For example  one could take a stricter definition of  height balanced   and require that the path length to the nearest empty child is within one of the path to the farthest empty child  My definition is less strict than that  and therefore admits more trees    One can also be less strict than my definition  one could say that a balanced tree is one in which the maximum path length to an empty tree on each branch differs by no more than two  or three  or some other constant  Or that the maximum path length is some fraction of the minimum path length  like a half or a quarter   It really doesn t matter usually  The point of any tree-balancing algorithm is to ensure that you do not wind up in the situation where you have a million nodes on one side and three on the other  Donal s definition is fine in theory  but in practice it is a pain coming up with a tree-balancing algorithm that meets that level of strictness  The performance savings usually does not justify the implementation cost  You spend a lot of time doing unnecessary tree rearrangements in order to attain a level of balance that in practice makes little difference  Who cares if sometimes it takes forty branches to get to the farthest leaf in a million-node imperfectly-balanced tree when it could in theory take only twenty in a perfectly balanced tree  The point is that it doesn t ever take a million  Getting from a worst case of a million down to a worst case of forty is usually good enough  you don t have to go all the way to the optimal case

User · Answer

This is being made way more complicated than it actually is   The algorithm is as follows    Let A   depth of the highest-level node Let B   depth of the lowest-level node If abs A-B   lt   1  then the tree is balanced

User · Answer

class Node       int data      Node left      Node right          assign variable with constructor     public Node int data            this data   data           public class BinaryTree        Node root          get max depth     public static int maxDepth Node node            if  node    null              return 0           return 1   Math max maxDepth node left   maxDepth node right                  get min depth     public static int minDepth Node node            if  node    null              return 0           return 1   Math min minDepth node left   minDepth node right                  return max-min lt  1 to check if tree balanced     public boolean isBalanced Node node             if  Math abs maxDepth node  - minDepth node    lt   1              return true           return false             public static void main String    strings            BinaryTree tree   new BinaryTree            tree root   new Node 1           tree root left   new Node 2           tree root right   new Node 3             if  tree isBalanced tree root               System out println  Tree is balanced            else             System out println  Tree is not balanced

User · Answer

Post order solution  traverse the tree only once  Time complexity is O n   space is O 1   it s better than top-down solution  I give you a java version implementation   public static  lt T gt  boolean isBalanced TreeNode lt T gt  root       return checkBalance root     -1     private static  lt T gt  int checkBalance TreeNode lt T gt  node       if node    null  return 0      int left   checkBalance node getLeft          if left    -1  return -1       int right   checkBalance node getRight          if right    -1  return -1       if Math abs left - right   gt  1           return -1       else          return 1   Math max left  right

User · Answer

include  lt iostream gt   include  lt deque gt   include  lt queue gt   struct node       int data      node  left      node  right      bool isBalanced node  root        if    root                return true             std  queue lt node   gt  q1      std  queue lt int gt   q2      int level   0  last level   -1  node count   0       q1 push root       q2 push level        while    q1 empty                   node  current   q1 front            level   q2 front             q1 pop            q2 pop             if   level                           node count                             if   current- gt left                                             q1 push current- gt left                           q2 push level   1                                      if   current- gt right                                             q1 push current- gt right                           q2 push level   1                              if   level    last level                         std  cout  lt  lt   Check     lt  lt   node count   node count - 1   1   lt  lt     Level     lt  lt  level  lt  lt     Old level     lt  lt  last level  lt  lt  std  endl              if   level  amp  amp   node count - 1      1  lt  lt   level-1                                   return false                             last level   q2 front                if   level   node count   1                       return true     int main         node tree 15        tree 0  left     amp tree 1       tree 0  right    amp tree 2       tree 1  left     amp tree 3       tree 1  right    amp tree 4       tree 2  left     amp tree 5       tree 2  right    amp tree 6       tree 3  left     amp tree 7       tree 3  right    amp tree 8       tree 4  left     amp tree 9        NULL      tree 4  right    amp tree 10       NULL      tree 5  left     amp tree 11       NULL      tree 5  right    amp tree 12       NULL      tree 6  left     amp tree 13       tree 6  right    amp tree 14       tree 7  left     amp tree 11       tree 7  right    amp tree 12       tree 8  left    NULL      tree 8  right    amp tree 10       tree 9  left    NULL      tree 9  right    amp tree 10       tree 10  left   NULL      tree 10  right  NULL      tree 11  left   NULL      tree 11  right  NULL      tree 12  left   NULL      tree 12  right  NULL      tree 13  left   NULL      tree 13  right  NULL      tree 14  left   NULL      tree 14  right  NULL       std  cout  lt  lt   Result     lt  lt  isBalanced tree   lt  lt  std  endl       return 0

User · Answer

Here is a version based on a generic depth-first traversal  Should be faster than the other correct answer and handle all the mentioned  challenges   Apologies for the style  I don t really know Java   You can still make it much faster by returning early if max and min are both set and have a difference  1   public boolean isBalanced  Node root         int curDepth   0  maxLeaf   0  minLeaf   INT MAX      if   root    null   return true      while   root    null             if   root left    null    root right    null                 maxLeaf   max  maxLeaf  curDepth                minLeaf   min  minLeaf  curDepth                      if   root left    null                 curDepth    1              root   root left            else               Node last   root              while   root    null               amp  amp    root right    null    root right    last                       curDepth -  1                  last   root                  root   root parent                            if   root    null                     curDepth    1                  root   root right                                    return   maxLeaf - minLeaf  lt   1

User · Answer

If this is for your job  I suggest    do not reinvent the wheel and  use buy COTS instead of fiddling with bits   Save your time energy for solving business problems

User · Answer

Bonus exercise response   The simple solution   Obviously in a real implementation one might wrap this or something to avoid requiring the user to include height in their response   IsHeightBalanced tree  out height      if  tree is empty          height   0         return true     balance   IsHeightBalanced tree left  heightleft  and IsHeightBalanced tree right  heightright      height   max heightleft  heightright  1     return balance and abs heightleft - heightright   lt   1

User · Answer

This only determines if the top level of the tree is balanced  That is  you could have a tree with two long branches off the far left and far right  with nothing in the middle  and this would return true  You need to recursively check the root left and root right to see if they are internally balanced as well before returning true

User · Answer

Balance is a truly subtle property  you think you know what it is  but it s so easy to get wrong  In particular  even Eric Lippert s  good  answer is off  That s because the notion of height is not enough  You need to have the concept of minimum and maximum heights of a tree  where the minimum height is the least number of steps from the root to a leaf  and the maximum is    well  you get the picture   Given that  we can define balance to be      A tree where the maximum height of any branch is no more than one more than the minimum height of any branch     This actually implies that the branches are themselves balanced  you can pick the same branch for both maximum and minimum    All you need to do to verify this property is a simple tree traversal keeping track of the current depth  The first time you backtrack  that gives you a baseline depth  Each time after that when you backtrack  you compare the new depth against the baseline   if it s equal to the baseline  then you just continue if it is more than one different  the tree isn t balanced if it is one off  then you now know the range for balance  and all subsequent depths  when you re about to backtrack  must be either the first or the second value    In code   class Tree       Tree left  right      static interface Observer           public void before            public void after            public boolean end              static boolean traverse Tree t  Observer o            if  t    null                return o end              else               o before                try                   if  traverse left  o                       return traverse right  o                   return false                finally                   o after                                      boolean balanced             final Integer   heights   new Integer 2           return traverse this  new Observer                 int h              public void before     h                  public void after     h--                public boolean end                     if  heights 0     null                        heights 0    h                    else if  Math abs heights 0  - h   gt  1                        return false                    else if  heights 0     h                        if  heights 1     null                            heights 1    h                        else if  heights 1     h                            return false                                                          return true                                      I suppose you could do this without using the Observer pattern  but I find it easier to reason this way      EDIT   Why you can t just take the height of each side  Consider this tree                                                                                                            C                                       A    B  D    E F  G H  J   OK  a bit messy  but each side of the root is balanced  C is depth 2  A  B  D  E are depth 3  and F  G  H  J are depth 4  The height of the left branch is 2  remember the height decreases as you traverse the branch   the height of the right branch is 3  Yet the overall tree is not balanced as there is a difference in height of 2 between C and F  You need a minimax specification  though the actual algorithm can be less complex as there should be only two permitted heights

User · Answer

Balancing usually depends on the length of the longest path on each direction  The above algorithm is not going to do that for you   What are you trying to implement  There are self-balancing trees around  AVL Red-black   In fact  Java trees are balanced

User · Answer

Here is a complete worked out tested solution in C   sorry I m no java dev   just copy paste in console app   I know that definition of balanced varies so not everyone may like my test results but please just look at the slightly different approach of checking depth height in a recursive loop and exiting on the first mismatch without saving node height level depth on each node  only maintaining it in a function call    using System  using System Linq  using System Text   namespace BalancedTree       class Program               public static void Main                           Value Gathering             Console WriteLine RunTreeTests new     0                  Console WriteLine RunTreeTests new int                       Console WriteLine RunTreeTests new     0  1  2  3  4  -1  -4  -3  -2                  Console WriteLine RunTreeTests null                Console WriteLine RunTreeTests new     10  8  12  8  4  14  8  10                  Console WriteLine RunTreeTests new int     20  10  30  5  15  25  35  3  8  12  17  22  27  32  37                   Console ReadKey                       static string RunTreeTests int   scores                        if  scores    null    scores Count      0                                return null                             var tree   new BinarySearchTree                 foreach  var score in scores                                tree InsertScore score                              Console WriteLine tree IsBalanced                  var sb   tree GetBreadthWardsTraversedNodes                 return sb ToString 0  sb Length - 1                        public class Node               public int Value   get  set            public int Count   get  set            public Node RightChild   get  set            public Node LeftChild   get  set            public Node int value                        Value   value              Count   1                     public override string ToString                         return Value         Count                     public bool IsLeafNode                         return LeftChild    null  amp  amp  RightChild    null                     public void AddValue int value                        if  value    Value                                Count                              else                               if  value  gt  Value                                        if  RightChild    null                                                RightChild   new Node value                                             else                                               RightChild AddValue value                                                           else                                       if  LeftChild    null                                                LeftChild   new Node value                                             else                                               LeftChild AddValue value                                                                              public class BinarySearchTree               public Node Root   get  set             public void InsertScore int score                        if  Root    null                                Root   new Node score                             else                               Root AddValue score                                    private static int  heightCheck          public bool IsBalanced                          heightCheck   0              var height   0              if  Root    null  return true              var result   CheckHeight Root  ref height               height--              return  result  amp  amp  height    0                      private static bool CheckHeight Node node  ref int height                        height                if  node LeftChild    null                                if  node RightChild    null  return false                  if   heightCheck    0  return  heightCheck    height                   heightCheck   height                  return true                            if  node RightChild    null                                return false                             var leftCheck   CheckHeight node LeftChild  ref height               if   leftCheck  return false              height--              var rightCheck   CheckHeight node RightChild  ref height               if   rightCheck  return false              height--              return true                      public StringBuilder GetBreadthWardsTraversedNodes                         if  Root    null  return null              var traversQueue   new StringBuilder                traversQueue Append Root                     if  Root IsLeafNode    return traversQueue              TraversBreadthWards traversQueue  Root               return traversQueue                     private static void TraversBreadthWards StringBuilder sb  Node node                        if  node    null  return              sb Append node LeftChild                     sb Append node RightChild                     if  node LeftChild    null  amp  amp   node LeftChild IsLeafNode                                  TraversBreadthWards sb  node LeftChild                             if  node RightChild    null  amp  amp   node RightChild IsLeafNode                                  TraversBreadthWards sb  node RightChild

User · Answer

The definition of a height-balanced binary tree is      Binary tree in which the height of the   two subtrees of every node never   differ by more than 1    So  An empty binary tree is always height-balanced   A non-empty binary tree is height-balanced if    Its left subtree is height-balanced  Its right subtree is height-balanced  The difference between heights of left  amp  right subtree is not greater than 1    Consider the tree       A               B              C   D   As seen the left subtree of A is height-balanced  as it is empty  and so is its right subtree  But still the tree is not height-balanced as condition 3 is not met as height of left-subtree is 0 and height of right sub-tree is 2   Also the following tree is not height balanced even though the height of left and right sub-tree are equal  Your existing code will return true for it          A                B    C               D        G               E            H   So the word every in the def is very important   This will work   int height treeNodePtr root            return   root    0  1   MAX height root- gt left  height root- gt right       bool isHeightBalanced treeNodePtr root            return  root    NULL                      isHeightBalanced root- gt left   amp  amp                  isHeightBalanced root- gt right   amp  amp                  abs height root- gt left  - height root- gt right    lt  1       Ideone Link

User · Answer

Wouldn t this work   return     Math abs  size  root left   - size  root right      lt  2      Any unbalanced tree would always fail this

User · Answer

An empty tree is height-balanced  A non-empty binary tree T is balanced if   1  Left subtree of T is balanced  2  Right subtree of T is balanced  3  The difference between heights of left subtree and right subtree is not more than 1      program to check if a tree is height-balanced or not     include lt stdio h gt   include lt stdlib h gt   define bool int     A binary tree node has data  pointer to left child    and a pointer to right child    struct node     int data    struct node  left    struct node  right         The function returns true if root is balanced else false    The second parameter is to store the height of tree       Initially  we need to pass a pointer to a location with value     as 0  We can also write a wrapper over this function    bool isBalanced struct node  root  int  height         lh -- gt  Height of left subtree       rh -- gt  Height of right subtree         int lh   0  rh   0          l will be true if left subtree is balanced      and r will be true if right subtree is balanced      int l   0  r   0     if root    NULL           height   0       return 1            Get the heights of left and right subtrees in lh and rh      And store the returned values in l and r         l   isBalanced root- gt left   amp lh     r   isBalanced root- gt right  amp rh         Height of current node is max of heights of left and       right subtrees plus 1         height    lh  gt  rh  lh  rh    1        If difference between heights of left and right       subtrees is more than 2 then this node is not balanced      so return 0      if  lh - rh  gt   2      rh - lh  gt   2       return 0        If this node is balanced and left and right subtrees      are balanced then return true      else return l amp  amp r         UTILITY FUNCTIONS TO TEST isBalanced   FUNCTION        Helper function that allocates a new node with the    given data and NULL left and right pointers     struct node  newNode int data        struct node  node    struct node                                   malloc sizeof struct node        node- gt data   data      node- gt left   NULL      node- gt right   NULL       return node      int main       int height   0        Constructed binary tree is              1                           2      3                       4     5  6          7           struct node  root   newNode 1       root- gt left   newNode 2     root- gt right   newNode 3     root- gt left- gt left   newNode 4     root- gt left- gt right   newNode 5     root- gt right- gt left   newNode 6     root- gt left- gt left- gt left   newNode 7      if isBalanced root   amp height       printf  Tree is balanced      else     printf  Tree is not balanced           getchar      return 0      Time Complexity  O n

User · Answer

Returns true if Tree is balanced  i e  if the difference between the longest path and the shortest path from the root to a leaf node is no more than than 1  This difference can be changed to any arbitrary positive number     boolean isBalanced Node root        if  longestPath root  - shortestPath root   gt  1          return false      else         return true      int longestPath Node root        if  root    null           return 0      else           int leftPathLength   longestPath root left           int rightPathLength   longestPath root right           if  leftPathLength  gt   rightPathLength              return leftPathLength   1          else             return rightPathLength   1           int shortestPath Node root        if  root    null           return 0      else           int leftPathLength   shortestPath root left           int rightPathLength   shortestPath root right           if  leftPathLength  lt   rightPathLength              return leftPathLength   1          else             return rightPathLength   1

User · Answer

public boolean isBalanced TreeNode root        return  maxDepth root  - minDepth root   lt   1      public int maxDepth TreeNode root        if  root    null  return 0       return 1   max maxDepth root left   maxDepth root right       public int minDepth  TreeNode root        if  root    null  return 0       return 1   min minDepth root left   minDepth root right

User · Answer

If binary tree is balanced or not can be checked by Level order traversal   private boolean isLeaf TreeNode root        if  root left    null  amp  amp  root right    null          return true      return false     private boolean isBalanced TreeNode root        if  root    null          return true      Vector lt TreeNode gt  queue   new Vector lt TreeNode gt         int level   1  minLevel   Integer MAX VALUE  maxLevel   Integer MIN VALUE      queue add root       while   queue isEmpty              int elementCount   queue size            while  elementCount  gt  0                TreeNode node   queue remove 0               if  isLeaf node                     if  minLevel  gt  level                      minLevel   level                  if  maxLevel  lt  level                      maxLevel   level                else                   if  node left    null                      queue add node left                   if  node right    null                      queue add node right                             elementCount--                    if  abs maxLevel - minLevel   gt  1                return false                    level               return true

User · Answer

Here s what i have tried for Eric s bonus exercise  I try to unwind of my recursive loops and return as soon as I find a subtree to be not balanced   int heightBalanced node  root       int i   1      heightBalancedRecursive root   amp i       return i       int heightBalancedRecursive node  root  int  i        int lb   0  rb   0       if  root       i      if node is null or a subtree is not height balanced            return 0         lb   heightBalancedRecursive root - gt  left i        if    i             subtree is not balanced  Skip traversing the tree anymore         return 0       rb   heightBalancedRecursive root - gt  right i       if  abs lb - rb   gt  1      not balanced  Make i zero           i   0       return   lb  gt  rb   lb  1   rb   1      return the current height of the subtree

User · Answer

To have a better performance specially on huge trees you can save the height in each node so it is a trade off space Vs performance   class Node       Node left      Node right      int value      int height      Example of implementing the addition and same for deletion   void addNode Node root int v       int height  0       while root    null                     Since we are adding new node so the height              will increase by one in each node we will pass by          root height    1           height             else if v  gt  root value               root   root left                           else           root   root right                                 height             Node n   new Node v   height            root   n             int treeMaxHeight Node root     return Math Max root left height root right height      int treeMinHeight Node root     return Math Min root left height root right height       Boolean isNodeBlanced Node root       if  treeMaxHeight root  - treeMinHeight root   gt  2         return false     return true     Boolean isTreeBlanced  Node root        if root    null    isTreeBalanced root left   amp  amp  isTreeBalanced root right   amp  amp  isNodeBlanced root       return true     return false

User · Answer

What balanced means depends a bit on the structure at hand   For instance  A B-Tree cannot have nodes more than a certain depth from the root  or less for that matter  all data lives at a fixed depth from the root  but it can be out of balance if the distribution of leaves to leaves-but-one nodes is uneven   Skip-lists Have no notion at all of balance  relying instead on probability to achieve decent performance   Fibonacci trees purposefully fall out of balance  postponing the rebalance to achieve superior asymptotic performance in exchange for occasionally longer updates   AVL and Red-Black trees attach metadata to each node to attain a depth-balance invariant    All of these structures and more are present in the standard libraries of most common programming systems  except python  RAGE     Implementing one or two is good programming practice  but its probably not a good use of time to roll your own for production  unless your problem has some peculiar performance need not satisfied by any off-the-shelf collections

[java] How to determine if binary tree is balanced?

Examples related to java

Examples related to algorithm

Examples related to data-structures

Examples related to binary-tree