CODEWITHSUNDEEP
javaalgorithmtree
Programmer
Programmer

Reputation: 6753

Height of a binary tree

Consider the following code:

public int heightOfBinaryTree(Node node)
{
    if (node == null)
    {
        return 0;
    }
    else
    {
        return 1 +
        Math.max(heightOfBinaryTree(node.left),
            heightOfBinaryTree(node.right));
    }
}

I want to know the logical reasoning behind this code. How did people come up with it? Does some have an inductive proof?

Moreover, I thought of just doing a BFS with the root of the binary tree as the argument to get the height of the binary tree. Is the previous approach better than mine?Why?

Upvotes: 37

Views: 85367

Answers (5)

f_i
f_i

Reputation: 3342

To extend more on the answers and elaborate more on recursion plus recursive call stack.

Suppose the tree

      2
     /\
    5  9
   /
  0

lets suppose the left sub-tree first, root(2) called the heightOfBinaryTree method on the left sub-tree

The call stack of the method in question will be as follows

node(5) calls node(0)
node(0) calls node(null)
node(null) breaks the recursive loop

consider that fact these calls are made before the method returned anything.

iterating back on the recursive call stack, this is where each node return its output.

node(null) returned 0 -> 0
node(0) returned (return from node(null) + 1) -> 1
node(5) returned (return from node(0) + 1) -> 2

Same goes for the right sub-tree. If we compare the output from both left and right sub-tree we will have the height.

Upvotes: 0

tiagovrtr
tiagovrtr

Reputation: 162

The height of a tree is the length of longest downward path from it's root. This function is a recursive way to count the levels of a binary tree. It just increments counters as it descends the tree, returning the maximum counter (the counter on the lowest node).

I hope I have helped.

Upvotes: 2

Adrian Mouat
Adrian Mouat

Reputation: 46480

It's a recursive function. It's saying the height of a tree is 1 + the height of its tallest branch.

Is BFS a breadth first search? I'm not sure what difference there would be in efficiency, but I like the simplicity of the recursive function.

Upvotes: 0

moinudin
moinudin

Reputation: 138317

if (node == null)
{
    return 0;
}

The children of leaf nodes are null. Therefore this is saying that once we've gone past the leaves, there are no further nodes.

If we are not past the leaf nodes, we have to calculate the height and this code does so recursively.

return 1 +

The current node adds a height of 1 to the height of the subtree currently being calculated.

    Math.max(heightOfBinaryTree(node.left),
        heightOfBinaryTree(node.right));

We recursively calculate the height of the left subtree (node.left) and right subtree (node.right). Since we're calculating the maximum depth, we take the maximum of these two depths.

I've shown above that the recursive function is correct. So calling the function on the parent node will calculate the depth of the entire tree.

Here's a graphical representation of the height of a tree from this document. h is the height of the tree, hl and hr are the heights of the left and right subtrees respectively.

Moreover, I thought of just doing a BFS with the root of the binary tree as the argument to get the height of the binary tree. Is the previous approach better than mine?Why?

The code you provided is a form of DFS. Since you have to process all nodes to find the height of the tree, there will be no runtime difference between DFS and BFS, although BFS will use O(N) memory while DFS will use O(logN) memory. BFS is also slightly more complex to code, since it requires a queue while DFS makes use of the "built-in" recursive stack.

Upvotes: 49

Shamim Hafiz - MSFT
Shamim Hafiz - MSFT

Reputation: 22064

The logic behind that code is:

since a node will have two children, the height of the Tree will be maximum of the heights of tree whose roots are the left child and right child, and of course +1 for the walk to the children.

As you can see, the description above is recursive and so is the code.

BFS should also do, but it would be an overkill as both implementation and space/time complexity.

There is a say, recursive functions though hard to understand, but are very elegant to implement.

Upvotes: 4

Related Questions