Binary tree depth

Question

Trying to find depth of binary search tree. Have done something with a bit of google search but my code is crashing:

int treeDepth(int depth) const
        {
            int l = this->left->treeDepth(depth);
            int d = this->right->treeDepth(depth);

            return depth + std::max(l, d);
        }

calling this function with: root->treeDepth(1);

Answer 1

First of all, I think that you may be confusing the depth of a tree with the height of a tree. Refer to What is the difference between tree depth and height? for an explanation.

For example, following are the depth and height of the nodes in this (binary) tree ('0' being the root):

    0     -- depth 0, height 2
   / \
  1   2   -- depth 1, height 1 and 2, respectively, for nodes 1 and 2
 / \
3   4     -- depth 2, height 0

As you can see, that the depth of the tree root is '0', which is O(1) computation. The height of the tree, however, is more interesting with regards to recursion and can be computed using the following:

struct TreeNode {
    T _value;
    typedef TreeNode* node_ptr;    
    node_ptr _left, _right;
};
...
int treeHeight(Node* node)
{
    return std::max(node->_left? 1 + height(node->_left) : 0,
                    node->_right? 1 + height(node->_right) : 0);
}
...
std::cout << treeHeight(root);
...

The fundamental idea is this: During the recursive (depth-first) traversal, if a leaf node is reached, return a value of '0' (which is the height of every leaf node). Otherwise, compute the height of the tree rooted at the non-leaf node (which is the max of the heights of the left subtree and the right subtree of that node + 1 for the node itself). Start from the root of the tree.

The second aspect that I want to address in your question is regarding what I gather from your function signature:

int treeDepth(int depth) const

and the way you are calling it:

root->treeDepth(1);

The depth of a tree is not conducive to being a property of the root. Instead, it is a property of the tree, which is composed of tree nodes, one of which is the root node. So, I would define the class (C++ struct shown here) as follows:

template<class T>
struct BinaryTree {
    struct TreeNode {
        T _value;
        typedef TreeNode* node_ptr;    
        node_ptr _left, _right;
    };
    TreeNode _root_node;
    typedef typename TreeNode::node_ptr node_ptr;
    node_ptr _root;
    ...
    int height(node_ptr node) const;
    ...
};

Finally, finding the depth of a given node in a tree:

int depth(node_ptr node) const;
// returns depth of node if it is in the tree, else -1

is a problem where you may apply recursion. However, a recursive approach is not natural and a breadth-first (or level-order) traversal will be more suited for this.

Answer 2

You need to read up a little bit about recursion.

One of the fundamental tenets of recursion is that there must be a "stop condition" which will at some point terminate the recursion.

Otherwise, you have what is known as "runaway recursion", your stack fills up, and your program crashes and burns.

In your case, a "stop condition" would be reaching a this->left or this->right which happens to be NULL.

So, for the future readers (as suggested by Barmar in a comment)

int l = left == NULL? 0 : left->treeDepth(depth);
int d = right == NULL? 0 : right->treeDepth(depth);

Answer 3

there are actually many problems in your code.

Fist of all you need to implement a recursion termination, that is a condition needed to stop your function from calling its self forever in your case you need to write something like if(left==nullptr && rigth==nullptr) return depth;

The recursion termination is VERY IMPORTANT! you always need it when you're writing a recursive function. Without you're 100% going into a never ending loop (in the best case).

then, when you re-call your function you need to change the depth value i mean, if you're going down on another node of the tree it means that the tree is tall at least "depth+1" so you need to pass depth + 1 not just depth, and at the and of the function just write

return std::max(l,d);

also,you're using pointers, always write a condition to check if you're really trying to access a well defined address, that is, before even trying to access an address (ex. this->left) you need to write a condition like if( this->left!=nullptr) (nullptr from c++ 11 otherwise NULL will as well get the work done)

Answer 4

try something like this:

int treeDepth() const
        {
            int l = left == NULL? 0 : left->treeDepth();
            int d = right== NULL? 0 : right->treeDepth();
            return 1 + std::max(l, d);
        }

In this case you don't need additional paramether "depth"