Recursion and Binary Trees

Question

#Get length of the longest path through recursion
def max_height(node):
    if not node:
        return 0
    left = max_height(node.left) #Base Case based on my understanding
    right = max_height(node.right) #Base Case based on my understanding
    return max_height(left, right) + 1

I keep calling the max_height to get the length but I'm getting an error. I've thought of three possibilities:

1) I misunderstand the concept of the base case and I don't actually have a base case.

2) I'm not properly spacing Python code.

3) I'm not recursively getting the height of the BST at all but rather the width of the tree, which is affecting later calculations.

I know it is similar to this question, but the main difference is that I'm really trying to use recursion , where the other question used iteration and merely called it recursion. how to find the height of a node in binary tree recursively

What error are you getting?

cyroxis
– cyroxis

2016-05-27 18:13:50 +00:00
Commented May 27, 2016 at 18:13 — cyroxis
– cyroxis, Commented May 27, 2016 at 18:13

Community · Accepted Answer · 2017-05-23 11:58:42Z

2

The base case is where the recursion stops and you have one: not node (node == None)
I don't see an issue with the spacing... Make sure you use only tabs or only spaces

This does produce the height: the number of nodes from root to leaf along the longest root-leaf path. At every node level, you add 1, and follow the higher subtree.

def max_height(node):
    if not node:  # this is the base case: 
        return 0  # where all recursive calls eventually stop
    left = max_height(node.left)    # <- these are the recursive calls:
    right = max_height(node.right)  # <- function x is called inside function x
    return max(left, right) + 1  # max here, not max_height

Note that this is merely a more verbose version of this answer to the question you linked.

edited May 23, 2017 at 11:58

CommunityBot

11 silver badge

answered May 27, 2016 at 17:00

user2390182

73.7k6 gold badges71 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Rasmi Ranjan Nayak · Accepted Answer · 2016-06-13 21:35:26Z

0

All answered were right but, I faced little problem while writing inside the class;

So, the code goes like this, I hope this helps.

    class Tree(object):
        def height(self, root):
            if root == None: #root == None
                return 0
            else:
                return 1 + max(self.height(root->left), self.height(root->left))
t = Tree()
t.height(t)

answered Jun 13, 2016 at 21:35

Rasmi Ranjan Nayak

12.1k30 gold badges90 silver badges127 bronze badges

Collectives™ on Stack Overflow

Recursion and Binary Trees

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related