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

Question

Hi all: i read the algorithm below to find the lowest 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 above function assumes that n1 is smaller than n2. Time complexity: O(n)Space complexity: O(1)

this algorithm is recursive,i know that when invoking a recursive function call,the function arguments and other related registers is pushed to the stack,so extra space is needed,on the other hand, the recursive depth is related to the size or height of the tree,say n,does it make more sense to be O(n)?

Thanks for any explanations here!

Answer 1

Although you are right to say that that recursive implementation of the algorithm requires O(n) space because of the stack space needed, it only uses tail recursion, meaning it can be reimplemented to use O(1) space with a loop:

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;
    }
}

(Note that else has to be added in to keep the semantics unchanged.)

Answer 2

This algorithm involves tail recursion. In the context of your question, the stack frame of the caller can be reused by the callee. In other words, all the nested sequence of function invocations are going to do is pass the result up like a bucket brigade. Consequently, only one stack frame is actually required.

For more reading, see Tail Call at the Wikipedia.