Finding height of tree without using list

Question

def height(t):
''' (Tree) -> int

Return 1 + the number of nodes in longest path in Tree t.

>>> tree = Tree(23)
>>> height(Tree)
1
>>> tree = descendents_from_list(Tree(11), [2, 3, 4, 5, 6], 3)
>>> height(tree)
3
'''
num = 1
for i in t.children:
    if i.children:
       num += height(i)
return num

For the above function with t.value and t.children, I need to figure out how to find the height WITHOUT using a list. Like I need to find a way to recursively go further down the tree without keeping track of parent trees.

I've tried it, but I can't figure it out. Can someone please help me out with this??

Shashank · Accepted Answer · 2015-03-23 23:14:46Z

2

The basic idea is this, the height of a tree is determined by the longest path in a tree. So if we are looking at a node with children, any node, which child node's height do we want to pay attention to? The child node with the highest height, correct? In Python, we can get the highest value of any iterable set of values using the built-in max function. At every point along the way, we want to add 1 to the maximum height amongst all of the children subtrees.

So now we just need a base case for the recursion, i.e. what do we do if a node has no children? Just return 1.

The following code illustrates this algorithm:

def height(t):
    if not t.children:
        return 1
    else:
        return max(height(c) for c in t.children) + 1

edited Mar 23, 2015 at 23:14

answered Mar 23, 2015 at 22:58

Shashank

13.9k5 gold badges39 silver badges63 bronze badges

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

Comments

itzMEonTV · Accepted Answer · 2015-03-23 23:17:17Z

0

Can you create a function for this like

num = 1
def height(t):
    global num
    child = [i for i in t if i.children]
    if child:
        num += 1
        height(child) #reccursing
    else:
        return num

answered Mar 23, 2015 at 23:17

itzMEonTV

20.4k4 gold badges44 silver badges53 bronze badges

Collectives™ on Stack Overflow

Finding height of tree without using list

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related