Nexus Archive

My attempt to traverse a tree without recursion

Trees are said to be recursive in nature, that means we actively use recursion to build and traverse them.

BUT...

I don't want to use recursion at first just because it's said to be used for trees. Obviously recursion is used for a reason but I want to see if I can traverse a tree without recursion, to see how big of a pain and inefficiency can it be, I want to see for myself. I wanna at least try to use traditional loop based approach that I did for other data structures like Array and linked lists !

🧠 This was my thought : Ok ! Now lets see how can We traverse a tree ! What if we use a head pointer that points to root (Linked list way) ? We can add another pointer and go DFS manner but after hitting a leaf node, we need to define another pointer at root and this time pick some other edge. Time complexity bumps up, 'cuz if there are 4 edges from root node the time complexity becomes bad like seriously bad because for every sub tree there can n number of nodes so it becomes....O(nn) ? That's bad very bad that can be infinite literally ! So the head concept wont work ! What if we use a std::vector to store each sub tree root ? Still not good approach because there can be n sub trees and each can grow to have n more sub trees so more or less same time complexity ! What else ? Hmm I can see linear way is bad !

Still upon thinking I cannot find an exact way to traverse them properly without using complex stuff like recursion. Trees have irregular structure and branching with no way to backtrack normally. But wait what if...we apply the logic of a doubly linked list ? An extra pointer that can point back to the parent ? If there is no parent then its the Root of the tree. But will add extra memory per node...

🔺 LETS TRY TO TRAVERSE USING A PARENT POINTER AND VISITED FLAG

#include<iostream>

typedef struct Node{
    int data;
    struct Node* left;
    struct Node* right;
    struct Node* parent;
    bool visited; //needed for DFS without recursion or external data structure to track visited nodes.
  
    Node() {}
    Node(int val) :
        data(val),
        left(nullptr),
        right(nullptr),
        parent(nullptr),
        visited(false) {}
        
}node;

  

void traverse(node* root){
    //trying a DFS traversal
    node* current = root;

    while(current != nullptr){

        //visit a node if it is not visited
        if(!current->visited){
            std::cout << current->data << std::endl;
            current->visited = true; //set visited to true
        }

        //if there exists a left node and its not visited
        if(current->left && !current->left->visited){
            current = current->left; //move current to that node (move down by 1 level)
        }

        //if there is no left node left we gotta visit the right ones, branch down right by one node.
        else if(current->right && !current->right->visited){
            current = current->right;
        }

        //backtrack ! If one of the levels are all visited we backtrack my moving current up by one level.
        else{
            current = current->parent;
        }
    }
}

int main(){

    node* root = new node(10);
    root->left = new node(8);
    root->right = new node(15);

    //setting the parent pointers
    root->left->parent = root;
    root->right->parent = root;
  
    //done this to avoid `->` chaining for better readability at the cost of 2 extra pointers in memory
    node* leftSubTree = root->left;
    node* rightSubTree = root->right;

    //left sub tree
    leftSubTree->left = new node(3);
    leftSubTree->right = new node(5);
    leftSubTree->left->parent = leftSubTree; //setting parent for left subtree
    leftSubTree->right->parent = leftSubTree;

    //right sub tree
    rightSubTree->left = new node(12);
    rightSubTree->right = new node(14);
    rightSubTree->left->parent = rightSubTree; //setting parent for right subtree
    rightSubTree->right->parent = rightSubTree;

    traverse(root);

    //free memory
    delete leftSubTree->left;
    delete leftSubTree->right;

    delete rightSubTree->left;
    delete rightSubTree->right;

    delete leftSubTree;
    delete rightSubTree;
  
    delete root;

    return 0;
}

The above code is an inefficient and rigid DFS approach. But clearly shows that using loops can be very difficult and will eventually make the whole code complex to understand, read and maintain. This convinced me that recursion is the way to go. Moreover I only encourage to do what I did if you really want to understand, poke around and like to question everything, the above is not practical enough but was fun to explore.

❌ Bad parts:

GO BACK TO TREES: Trees.

#CPP #Data Structures And Algorithms