Why is the spatial complexity of this algorithm O (1)

Question

Hi everyone: I read the algorithm below to find the least common ancestor of two nodes in a binary search tree.

 /* A binary tree node has data, pointer to left child
   and a pointer to right child */
 struct node
 {
  int data;
  struct node* left;
  struct node* right;
 };

 struct node* newNode(int );

/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
 /* If we have reached a leaf node then LCA doesn't exist
 If root->data is equal to any of the inputs then input is
 not valid. For example 20, 22 in the given figure */
 if(root == NULL || root->data == n1 || root->data == n2)
 return -1;

 /* If any of the input nodes is child of the current node
 we have reached the LCA. For example, in the above figure
 if we want to calculate LCA of 12 and 14, recursion should
 terminate when we reach 8*/
 if((root->right != NULL) &&
  (root->right->data == n1 || root->right->data == n2))
  return root->data;
 if((root->left != NULL) &&
 (root->left->data == n1 || root->left->data == n2))
 return root->data;   

 if(root->data > n1 && root->data < n2)
   return root->data;
 if(root->data > n1 && root->data > n2)
  return leastCommanAncestor(root->left, n1, n2);
 if(root->data < n1 && root->data < n2)
  return leastCommanAncestor(root->right, n1, n2);
}    

Note that the above function assumes that n1 is less than n2. Difficulty of time: O (n) Difficulty of space: O (1)

this algorithm is recursive, I know that when calling a call to a recursive function, the function arguments and other related registers are pushed onto the stack, so additional space is required, on the other hand, the recursive depth is related to the size or height of the tree, say n, does it make sense to be O ( n)?

Thanks for any explanation here!

Answer 1

, O (n) - , , O (1)

int leastCommanAncestor(struct node* root, int n1, int n2)
    while (1)
    {
     /* If we have reached a leaf node then LCA doesn't exist
     If root->data is equal to any of the inputs then input is
     not valid. For example 20, 22 in the given figure */
     if(root == NULL || root->data == n1 || root->data == n2)
     return -1;

     /* If any of the input nodes is child of the current node
     we have reached the LCA. For example, in the above figure
     if we want to calculate LCA of 12 and 14, recursion should
     terminate when we reach 8*/
     if((root->right != NULL) &&
      (root->right->data == n1 || root->right->data == n2))
      return root->data;
     if((root->left != NULL) &&
     (root->left->data == n1 || root->left->data == n2))
     return root->data;   

     if(root->data > n1 && root->data < n2)
       return root->data;
     if(root->data > n1 && root->data > n2)
      root = root->left;
     else if(root->data < n1 && root->data < n2)
      root = root->right;
    }
}

( , else , .)

Answer 2

. . , , , -. , .

Tail Call .