Node search in Binary Tree overflows stack

Question

I use the following method to traverse* a binary tree of 300 000 levels:

Node* find(int v){
   if(value==v)
      return this;
   else if(right && value<v)
      return right->find(v); 
   else if(left && value>v)
      return left->find(v);
}

However I get a segmentation fault due to stack overflow. Any ideas on how to traverse the deep tree without the overhead of recursive function calls?

* By "traverse" I mean "search for a node with given value", not full tree traversal.

Answer 1

Yes! For a 300 000 level tree avoid recursion. Traverse your tree and find the value iteratively using a loop.

Binary Search Tree representation

           25             // Level 1
        20    36          // Level 2
      10 22  30 40        // Level 3
  .. .. .. .. .. .. .. 
.. .. .. .. .. .. .. ..   // Level n

Just to clarify the problem further. Your tree has a depth of n = 300.000 levels. Thus, in the worst case scenario a Binary Search Tree (BST) will have to visit ALL of the tree's nodes. This is bad news because that worst case has an algorithmic O(n) time complexity. Such a tree can have:

2ˆ300.000 nodes = 9.9701e+90308 nodes (approximately).

---

9.9701e+90308 nodes is an exponentially massive number of nodes to visit. With these numbers it becomes so clear why the call stack overflows.

---

Solution (iterative way):

I'm assuming your Node class/struct declaration is a classic standard integer BST one. Then you could adapt it and it will work:

struct Node {
    int data;
    Node* right;
    Node* left;
};

Node* find(int v) {
    Node* temp = root;  // temp Node* value copy to not mess up tree structure by changing the root
    while (temp != nullptr) {
        if (temp->data == v) {
            return temp;
        }
        if (v > temp->data) {
            temp = temp->right;
        }
        else {
            temp = temp->left;
        }
    }
    return nullptr;
}

Taking this iterative approach avoids recursion, hence saving you the hassle of having to recursively find the value in a tree so large with your program call stack.