Tree is a frequently used data structure that simulates a tree structure. Each node of the tree will have a root value and a list of subtrees of child nodes. There are 3 different ways to traverse all nodes in the tree.
Pre-order Traversal (NLR)
Visit the root node first. Then, visit the left subtree. Finally, proceed with the right subtree.
In-order Traversal (LNR)
Visit the left subtree first. Then visit the root, and finally visit the right subtree.
Typically for binary search tree, using In-order Traversal will return all data in sorted order
Post-order Traversal (LRN)
Visit the left subtree first. Then right subtree, and finally root.
When you delete a node from tree, deletion proceeds in post-order. It means you will delete the left subtree first, and its right subtree before you delete the node itself.
Post-order is widely used in mathematical expression. Here is an example
To make a program that handles this mathematical expression, you can use post-order traversal along with stack.
Each time when you meet an operator, pop 2 elements from the stack, and calculate the result and push the result back into the stack.
Implementation
- Implementing using recursion is relatively simpler than proceeding iteratively. We can use stack to implement iterative traversal.
- https://github.com/youngkih/leetcode-examples/tree/master/src/tree/binary_tree_traversal
Binary Tree Level Order Traversal
Level order traversal is to traverse the tree level by level.
- Breadth-First Search is an algorithm that visits nodes in level order.
- We can use queue to implement BFS
Will the Guru 
Leave a comment