Hello. I was just wondering if there was a name for the pictured tree traversal? All other forms of traversal I have seen never follow this pattern.

For some context I am using a tree structure to calculate some things which requires traveling backwards and then forwards again.

What would be the best way of traversing a structure in this manner? Recursion? If possible, examples would be lovely. Thank you everyone.

Edit: I forgot to mention the red boxed node is an impossible node that would be ignored in the case I will be using this in. Shouldn't change much though.

CodePudding user response：

looks like depth-first with end-recursion eliminated.

hende 9->3 and 12 as the end point.

5,10 is some special case still not adequately explained in the question.

The folks on CS may have a better idea.

CodePudding user response：

Overall there are 3 types of tree traversal.

In-Order Traversal

In-order traversal means to visit the left branch, then the current node, and finally, the right branch

void InOrderTraversal(Node *node) {
     if (node != nullptr) {
        InOrderTraversal(node->left);
        visit(node);
        InOrderTraversal(node->right);    
     }
} 

Pre-Order Traversal

Pre-order traversal visits the current node before its child nodes

void PreOrderTraversal(Node *node) {
     if (node != nullptr) {
        visit(node);
        PreOrderTraversal(node->left);
        PreOrderTraversal(node->right);    
     }
} 

In pre-order traversal, the root is always the first node visited

Post-Order Traversal

Post-order traversal visits the current node after its child nodes

void PostOrderTraversal(Node *node) {
     if (node != nullptr) {
        PostOrderTraversal(node->left);
        PostOrderTraversal(node->right);    
        visit(node);
     }
} 

In post-order traversal, the root is always the last node visited

If I read your image right, you have post-order traversal.