# 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):

#Write your code here

if root is not None:

inOrder(root.left)

sys.stdout.write(str(root.data)+str(' '))

inOrder(root.right)

def PreOrder(root):

#Write your code here

if root is not None:

sys.stdout.write(str(root.data)+str(' '))

PreOrder(root.left)

PreOrder(root.right)

def PostOrder(root):

#Write your code here

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