How to find node height in binary tree recursively

Question

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 example code for finding height, defined as the length of a long path by the number of nodes from itself to the sheet. Node leaf height is 1.

he does not work.

Answer 1

What you do is not recursive, iterative. A recursive would look something like this:

 def height(node): if node is None: return 0 else: return max(height(node.left), height(node.right)) + 1 

Answer 2

You got a solution from mata, but I suggest you also look at your code and understand what it does:

  while self.right != None: self = self.right path = path +1 

What will it be? he will find the right child, then his right child, etc. Thus, it checks only one path of the "rightmost" sheet.

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 subtask, you solve it using the same recipe for all the other subtasks. Therefore, if you apply your algorithm only to a subtree or to a sheet, it will still work.

In addition, the recursive definition invokes itself (although you can implement this with a loop, but it is out of scope).

Recall the definition:

Recursion: see definition of recursion.

;)

Answer 3

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

Answer 4

 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 think that each magnifying edge is a height. Skip hackerrank test sites