Tree traversals
A Binary tree is a hierarchical data structure that contains at most two children.
There are three different ways of visiting the binary tree nodes,
- Pre order traversal – ( Node, Left, Right)
- In order traversal – (Left, Node, Right)
- Post order traversal – (Left, Right, Node)
Pre Order Traversal
def pre_order(root, result):
if root is None:
return result
result.append(root.val)
pre_order(root.left, result)
pre_order(root.right, result)
return result
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
return pre_order(root, [])
In Order Traversal
def inorder(root, result):
if not root:
return result
inorder(root.left, result)
result.append(root.val)
inorder(root.right, result)
return result
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
return inorder(root, [])
Post Order Traversal
def post_order(root, result):
if root is None:
return result
post_order(root.left, result)
post_order(root.right, result)
result.append(root.val)
return result
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
return post_order(root, [])
All these recursion solutions are trivial. But could you come up with iterative solutions for these traversals?
Srini's Blog 