CODEWITHSUNDEEP
algorithmrecursiondata-structures
s-o-i-a
s-o-i-a

Reputation: 25

How recursion is used in tree

I am new to tree concept in data structure. I can write a linear code for simple tree problems but i was struggled very much when i try to convert that into recursive code. And i can't write a recursive code for complex tree problems. But i know how tree works. I faced the problem when i try to convert the linear code into recursive for the problem "Finding the height of the tree" I can draw it and imagine the flow on paper. But I can't write a recursion.

Upvotes: 2

Views: 236

Answers (2)

Mureinik
Mureinik

Reputation: 311088

The key point here is to understand that every node of the tree is a tree in its own right. This is, in fact, what allows you to implement a recursive algorithm. As you may know, any recursive algorithm needs two parts:

  1. A stop criterion. In this case, we'll define an empty (null) tree's height as 0.
  2. A recursive part. In this case, we can say that the height of a tree is 1 plus the height of its deepest child.

So, e.g., if we implemented this in Java:

public static int height(Node n) {
    if (n == null) {
        return 0;
    }
    return 1 + Math.max(height(n.getLeft()), height(n.getRight()));
}

Upvotes: 4

Joe
Joe

Reputation: 111

The height of any node, is the height of its 'tallest' child node + 1. So starting at the root, you recursively call your find height function on each child node, select the biggest, add 1, and return that value. The base case would be a node with no children, in which case return 0.

Upvotes: 1

Related Questions