CODEWITHSUNDEEP
javascriptbinary-tree
user17953749
user17953749

Reputation: 15

find max. leaf nodes of a binary tree

       50
     /    \ 
   25      75
  /  \     / \
 15  27   62  79  

depth = 3
total nodes = 7
max leaf nodes = 4

       50
     /    \ 
   25      75
  /  \     / \
 15  27   62  79  
 _    _   _    _ 
 1    1   1    1  = 4

in a case where the Tree is full this will find the total amount of leaf nodes, but if the tree is not full and only the depth of the tree is known how can i know the max. leaf nodes in that tree?

// if the tree is full
function total_leafs_nodes(node, level, mxlevel)
  {
      if (node == null) {
        return 1;
      }
      if (node.left == null && node.right == null)
          return 1;

      else if (level == mxlevel)
      {
          return 1;
      }
      return (total_leafs_nodes(node.left, level + 1, mxlevel)
      + total_leafs_nodes(node.right, level + 1, mxlevel));
  }

Upvotes: 1

Views: 409

Answers (1)

Hangover Sound Sound
Hangover Sound Sound

Reputation: 192

If there is a max number of child nodes that every node can have, then you can apply the following :

Let d equal the depth, m the number of max child nodes per node, and n the number of possible nodes, then...

n = m ^ (d - 1)

Upvotes: 1

Related Questions