Binary Trees

Preorder Traversal

Pre-order traversal is to visit the root first. Then traverse the left subtree. Finally, traverse the right subtree.

Basically, visits its current node before its child node (hence pre-order)

Pre-order is implemented as a queue in iterative.

Used to create a copy of the tree or get prefix traversal.

Queues

fn preOrderTrav(TreeNode Node){
	if node != None:
		visit(node);
		preOrderTrav(node.left)
		preOrderTrav(node.right)
}

In-order traversal

In-order traversal is to traverse the left subtree first. Then visit the root. Finally, traverse the right subtree.

In-order is implemented as a stack in iterative.

When performed on a binary search tree, it visits the nodes in ascending order (hence the name in-order)

Stacks

fn inOrderTrav(TreeNode node){
	if node != None:
		inOrderTrav(node.left)
		visit(node)
		inOrderTrav(node.right)
}

Post Order

Visits current node after its child nodes (post-order, as it does its node post)

In a post order, the root is always visited last.

Used to delete trees or postfix expression.

fn postTrav(TreeNode node){
	postTrav(node.left)
	postTrav(node.right)
	visit(node)
}