I am testing myself on some personal learning topics and here are my Q & A’s. Underlined words indicate an area I need to investigate and understand better. Study was mainly done here
WHAT IS TREE TRAVERSAL?
Tree traversal in this context is the programmatic visitation to nodes in a tree. In my mind is a BST with data and left and right pointers. The process that a program uses to visit and perform computation on the trees nodes is tree traversal.
WHEN PERFORMING TREE TRAVERSAL WHAT STEPS ARE AVAILABLE FOR THE PROGRAM TO PROCESS ALL NODES?
- Answer the question “Are both of this nodes left and right pointers null?”
- Process the nodes data
- Traverse to the left node and repeat
- Traverse the right node and repeat
Except for the null check, the steps can be performed in any order.
WHAT STRATEGIES EXIST FOR TRAVERSING ALL BST TREE NODES AND HOW DO THEY WORK?
Given the following designations for operations:
- (N) Process node N
- (L) recursively traverse the left sub tree
- (R) recursively traverse the right sub tree
There are four types of traversals:
- Post Order traversal when at Node N
- Check if N is empty or null
- (L) recursively traverse the left subtree and end up back at N
- (R) recursively traverse the right subtree and end up back at N
- (N) process the node N
- In Order Traversal when at Node N
- Check if N is empty or null
- (L) recursively traverse the left subtree and end up back at N
- (N) process the node N
- (R) recursively traverse the right subtree and end up back at N
- Pre Order traversal when at Node N
- Check if N is empty or null
- (N) process the node N
- (L) recursively traverse the left subtree and end up back at N
- (R) recursively traverse the right subtree and end up back at N
- Breadth First Search (BFS)
- A strategy that visits each level of a BST, progressively getting deeper and processing each level
- Implementation is through Queue
TYPES OF PROBLEMS
Each traversal strategy is adept at solving certain problems.
PRE-ORDER
Can be used to duplicate nodes and edges to make a duplicate binary tree. For expression trees it can be used to make a prefix expression (polish notation)
IN-ORDER
Binary search trees commonly use in-order traversal. In-order traversal returns the values from the underlying set (in order) according to the comparator that that set up the BST.
POST-ORDER
Post-order traversal, while deleting or freeing nodes and values, can delete or free an entire binary tree. It can also generate a postfix representation of the binary tree.
