Finding the depth of a Binary Tree

Question

Hi I am trying to find the depth of the binary tree. I was trying a different method than the conventional way to do it. My logic is trying to find max of the levels while doing a depth traversal. Following is the code. This approach is not working as the max value is always zero once it reaches the else part. I am not understanding why.

public class BinaryTree {

    public static void main(String args[])
    {
        Node root = new Node(1);
        Node two = new Node(2);
        Node three = new Node(3);
        Node four = new Node(4);
        Node five = new Node(5);
        Node six = new Node(6);
        Node seven = new Node(7);
        Node eight = new Node(8);

        root.left = two;
        root.right = three;
        two.left = four;
        two.right = five;
        three.left = six;
        three.right = seven;
        five.left = eight;
        findDepth(root,0,0);

    }


    public static void findDepth(Node root,int level, int max)
    {

        if(root==null)
            return ;
        else{

            if(root.left==null && root.right==null)
            {
                if(max<level)
                {

                    max=level;

                }
                level=level-1;
            }

            findDepth(root.left,level+1,max);
            findDepth(root.right,level+1,max);

        }
    }

}

// The Node class

public class Node {

    int data;
    Node left;
    Node right;

    public Node(int i) {
        this.data = i;
    }

}

I did this and it worked perfectly

public static int findDepth(Node root,int level, int max1, String str)
{

    if(root==null)
        return 0;

    if(max<level)
    {

        max=level;

    }
        findDepth(root.left,level+1,max,"left");
        findDepth(root.right,level+1,max,"right");

        return max;

}

Here max is static member of the class. But i want to point out to another article in stack overflow where they said the value will propagate down to the next recursive call.

Print all paths from root to leaf in a Binary tree

Here the old value of list is getting propagated to all recursive calls

Answer 1

As an argument variable, max will behave like a local variable. Meaning each recursion will have it's own copy of the variable max. And since you are not returning anything back, you will throw that value away, so by the end of the whole recursion the value of max in the first call into the function is still zero.

Consider making max a static variable within the function instead of passing it as an argument.

As an aside, your approach still has a problem that your function findDepth doesn't "find" anything since it's not returning anything. You could also return max at each level but ignore it always, so only the caller into findDepth actually deals with max. But this approach is gently nudging you back towards the original way to do it :).

Update

Asker had a follow up question.

But i want to point out to another article in stack overflow where they said the value will propagate down to the next recursive call.

As user430788 explained, max is a primitive type int, passed by value, while the ArraList<Integer> is not, so it will be passed by reference and will be shared by all instances of that function call.

Answer 2

Max is a primitive type. All Java primitive types are passed by value so changing them inside a function does not effect their value in the caller.

You need to return the new max. Also, your recursive code is a bit wonky.

Try this...

public class BinaryTree {

    public static void main(String args[])
    {
        Node root = new Node(1);
        Node two = new Node(2);
        Node three = new Node(3);
        Node four = new Node(4);
        Node five = new Node(5);
        Node six = new Node(6);
        Node seven = new Node(7);
        Node eight = new Node(8);

        root.left = two;
        root.right = three;
        two.left = four;
        two.right = five;
        three.left = six;
        three.right = seven;
        five.left = eight;
        findDepth(root,0,0);

    }


    public static int findDepth(Node root,int level)
    {

        if(root==null){
            return level;
        }else{
            return Math.Max(findDepth(root.left,level+1,max),
                            findDepth(root.right,level+1,max));
        }
    }

}

// The Node class

public class Node {

    int data;
    Node left;
    Node right;

    public Node(int i) {
        this.data = i;
    }

}

When you call it to start with it should be called as findDepth(treeRoot,0);

What the recursive logic is saying is "as we go down the tree, increment level by 1 for each layer. When we hit the bottom, return level. Then for every node above the bottom, take the levels returned by the two nodes below us and return the deeper level.