Trees and Recursion

Tree is a natural data structure for recursion.

Recursion algorithm normally is concise yet abstract: we don’t need to write out the whole cookbook, instead, we outline the blueprint (which is implemented by the function itself but with the parameter of a smaller value).

Case study: Never underestimate the magic power of the following classic and simple problems of tree traversal.

"""
Node is defined as
self.left (the left child of the node)
self.right (the right child of the node)
self.data (the value of the node)
"""
import sys
def inOrder(root):
if root is not None:
inOrder(root.left)
sys.stdout.write(str(root.data)+str(' '))
inOrder(root.right)
def PreOrder(root):
if root is not None:
sys.stdout.write(str(root.data)+str(' '))
PreOrder(root.left)
PreOrder(root.right)
def PostOrder(root):
if root is not None:
PostOrder(root.left)
PostOrder(root.right)
sys.stdout.write(str(root.data)+str(' '))

Just be the dictator and decompose your supreme power down to subtasks under the same glory name of yours. Of course, be careful of the terminate case.

# Tree: Height of a Binary Tree
def height(root):
if root is None:
return 0
left = height(root.left)
right = height(root.right)
return max(left,right)+1
Like what you read? Give DJ Deustch a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.