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.
-
Not sure what exactly your problem is, but recursion works on trees exactly the same way it works elsewhere. The key is identifying a recurring/repeated piece of logic and then just code it as a function that calls itself.Sergio Tulentsev– Sergio Tulentsev2017-03-03 17:53:47 +00:00Commented Mar 3, 2017 at 17:53
-
1You need to study inorder.preorder.postorder traversal first and their . Codes are just 4 lines for each of them then every new level you enter while traversing add the counterminigeek– minigeek2017-03-03 17:54:22 +00:00Commented Mar 3, 2017 at 17:54
Add a comment
|
2 Answers
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:
- A stop criterion. In this case, we'll define an empty (null) tree's height as 0.
- 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()));
}
Comments
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.
Comments
