path = 0 # the lenght of the path
while self.right != None or self.left != None:
while self.right != None:
self = self.right
path = path +1
while self.left != None:
self = self.left
path = path +1
return path
this is my sample code for find the Height, is defined as the length of the longest path by number of nodes from self to a leaf. The height of a leaf node is 1.
it doesn't work.
What you're doing isn't recursive, it's iterative. Recursive would be something like:
def height(node):
if node is None:
return 0
else:
return max(height(node.left), height(node.right)) + 1
return -1, which means a leaf would have a height of 0 (which is usually how the hight of a tree is defined), but the OP specified "The height of a leaf node is 1", so that's probably why I changed it.
None for node.left and node.right, therefore ending the recursion there, there's no need to treat leaf or inner or root nodes differently.You were given the solution by mata, but I suggest you also look at your code and understand what it is doing:
while self.right != None:
self = self.right
path = path +1
What will this do? it will find the right child, then its right child, and so on. So this checks only one path of the "rightmost" leaf.
This does the same for the left:
while self.left != None:
self = self.left
path = path +1
The idea in recursion is that for each subproblem, you solve it using the exact same recipe for all other subproblems. So if you would apply your algorithm only to a subtree or a leaf, it would still work.
Also, a recursive definition calls itself (although you can implement this with a loop, but that is beyond the scope here).
Remeber the definition:
Recursion: see definition of Recursion.
;)
def height(node):
if node is None:
return 0
else:
if node.left==None and node.right==None:
return max(height(node.left), height(node.right))+0
else:
return max(height(node.left), height(node.right))+1
If you consider each increasing edge to be the height. To pass hackerrank testcases
def getHeight(self, root):
if root == None:
return -1
else:
return 1 + max( self.getHeight(root.left), self.getHeight(root.right) )
Here is the complete program in Python ::
class Node :
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def maxDepth(node):
if node is None :
return 0
else :
ldepth = maxDepth(node.left)
rdepth = maxDepth(node.right)
if (ldepth>rdepth):
return ldepth +1
else :
return rdepth +1
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print "Height of tree is %d" %(maxDepth(root))
Source : here
def height(self):
if self.root !=None:
return self._height(self.root,0)
else:
return 0
def _height(self,cur_node,cur_height):
if cur_node==None :
return cur_height
left_height = self._height(cur_node.left_child,cur_height+1)
right_height = self._height(cur_node.right_child,cur_height+1)
return max(left_height,right_height)
