Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Trying to find depth of binary tree

binary tree c++

This topic has been archived. This means that you cannot reply to this topic.
1 reply to this topic

#1 sonar87

sonar87

    CC Newcomer

  • Member
  • PipPip
  • 20 posts

Posted 12 April 2017 - 03:06 PM

I'm trying to write something to determine the largest depth of a binary tree but far have only ended up with one thing that keep giving back the number of nodes in the tree, and another, below, that is always one more or less off. After hours of trying to adjust this I could really use some advice..

void findthedepth(nodeoftree<node>* root, int* depthtotal, int* depthcurrent){

        int left = 0, right = 0;

       if( root == nullptr ){
           *depthtotal = 0;
           *depthcurrent = 0;
           return;
       }

       findthedepth(root->rightp(), depthtotal, depthcurrent);
       right = *depthcurrent;

       *depthcurrent = 0;

       findthedepth(root->leftp(), depthtotal, depthcurrent);
       left = *depthcurrent;


       if (left > right){ 
           *depthtotal += left + 1;
       }
       else { 
           *depthtotal += right + 1;
       }


   }


#2 Gikoskos

Gikoskos

    CC Newcomer

  • Member
  • PipPip
  • 21 posts

Posted 16 April 2017 - 03:04 AM

The depth of a binary tree is given by the binary logarithm of the total nodes on the tree. If you store an extra 'unsigned int' info on your tree data structure, that serves as a counter for the nodes on the tree, you can simply calculate the depth of the tree with this formula:

#include <cmath>

depth = (unsigned int)std::floor(std::log2(total_nodes));

Although I'm guessing that you don't have a tree data structure, but instead you store simply the pointer to the root of the tree. You can make a tree class/struct wrapper, and store in it the number of the nodes and the root pointer. After doing that, it's easy to calculate the depth using the above formula. Don't forget to increment/decrement the number of total nodes, every time you do an insertion/deletion.

 

It's possible to calculate it without storing the number of total nodes, but you'd have to follow all possible paths from the root to every NIL node, and then find the 'max' path. It's far too expensive though, in contrast with simply storing the total nodes separately, and just performing the above calculation.