Binary search Tree balanced working for getting height

Question

I know this is pretty straight forward code but wondering how exactly the internal working is.

public static int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
            System.out.print(getHeight(root.left) +"\t");
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }

For my understanding, I added print statement but it results the following.

printing root.left() prints this: 0 0 0 1 0 0 0

printing root.right() prints this: 0 0 2 0 0 3 0 0 2 0 0 0 1 0

Following is the Tree created in the main program:

TreeNode parent = new TreeNode(10);

        parent.insertInOrder(2);
        parent.insertInOrder(13);
        parent.insertInOrder(5);
        parent.insertInOrder(6);
        parent.insertInOrder(15);
        parent.insertInOrder(6);

How is this printing the above result and how is it working. If anyone can explain me with the above example, it would really help me.

I know how traversals work and how to print the tree but I really want to understand the above output. If anyone can help then it would be great.

void setLeftChild(TreeNode left)
    {
        this.left = left;
        if(left == null)
        {
            left.parent = this;
        }
    }

    void setRightChild(TreeNode right)
    {
        this.right = right;
        if(right == null)
        {
            right.parent =  this;
        }
    }

    void insertInOrder(int d)
    {
        if(d <= data)
        {
            if(left == null)
            {
                setLeftChild(new TreeNode(d));
            }
            else
            {
                left.insertInOrder(d);
            }
        }
        else{
            if(right == null)
            {
                setRightChild(new TreeNode(d));
            }
            else{
                right.insertInOrder(d);
            }
        }
        size++;
    }

is size a global variable? And are you doing any balancing here or is it an unbalanced bst? As a side note, do insertion using an iterative code. Try to avoid recursion if you can. They are slow. — arunmoezhi
what part of the code does the balance? If size isn't global how will its value propagate in the recursive calls. You have to pass it in the recursive function as a parameter. — arunmoezhi
My question is not all related to what ur asking.. no issues with rest of the code — fscore

Jim Mischel Jim Mischel · Accepted Answer · 2014-05-02T12:57:31

You should create a function that outputs information about the tree. For example, this function does a preorder traversal, showing information about each node:

public static void ShowTree(TreeNode root, TreeNode parent, depth)
{
    if (root == null) return;

    // output 'depth' spaces.
    // The indentation will help show the structure of the tree.        

    // output node value, and parent (if parent not null)

    // Traverse the left node
    ShowTree(root.left, root, depth+1);

    // Traverse the right node
    ShowTree(root.right, root, depth+1);
}

Call that function with ShowTree(tree, null, 0). The resulting output will show the structure of the tree, and you can determine if the tree is balanced. It's a useful thing to have when you're developing tree code because you can do an insert, for example, then call ShowTree to see if the insert worked as expected.

Update

The code's output is a little strange because your print statement results in a recursive call. So every node below the current node ends up getting printed multiple times.

I think you want to do this:

int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
// now output output leftHeight or rightHeight, or both
return Math.max(leftHeight, rightHeight) + 1;

That way you won't get the multiple recursive calls that produce the strange output.

More info

The reason you're seeing those extra recursive calls is because you're calling getHeight(root.left) twice. Let's say your tree looks like this:

       root
      /
   child
   /
grandchild

So you call getHeight(root). Then:

getHeight(child) is called in your print statement
getHeight(grandchild) is called in your print statement
getHeight(null) is called in your print statement
getHeight(grandchild) prints 0
getHeight(null) is called twice (once for the left node and once for the right node) in the return statement
getHeight(grandchild) returns 1
getHeight(child) prints 1
getHeight(grandchild) is called in the return statement
getHeight(null) is called in your print statement
getHeight(grandchild) prints 0
getHeight(grandchild) returns 1
getHeight(null) (the right node) is called in the return statement
...

You see where the problem is? getHeight(grandchild) is called again! Every time your print statement calls getHeight, it has to walk every descendant node. So the height of every node is output multiple times. The deeper the node is in the tree, the more often it will be output.

The change I suggested in my update above prevents that by ensuring that no node is visited more than once.

Binary search Tree balanced working for getting height

1 Answers

Update

More info