Achieving Time Complexity O(n) - Searching Preorder Binary Tree C-CodePudding

Binary Search Tree LCA Have the function BinarySearchTreeLCA(strArr) take the array of strings stored in strArr, which will contain 3 elements: the first element will be a binary search tree with all unique values in a preorder traversal array, the second and third elements will be two different values, and your goal is to find the lowest common ancestor of these two values. For example: if strArr is ["[10, 5, 1, 7, 40, 50]", "1", "7"] then this tree looks like the following:

        10
       /  \
      5    40
     / \    \
    1   7    50

For the input above, your program should return 5 because that is the value of the node that is the LCA of the two nodes with values 1 and 7. You can assume the two nodes you are searching for in the tree will exist somewhere in the tree.

When submitting my code for this challenge the website calculates my time complexity to be O(n^2) when the most efficient is O(n). I believe that the problem lies within the "build tree" function because the for loop calls a recursive "build tree". Please help me identify what is causing my time complexity to be quadratic and the concept to achieve a linear time complexity

    #include <iostream>
    #include <string>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    using namespace std;

    struct Node {
        int value;
        Node *parent = nullptr;
        Node *leftChild = nullptr;
        Node *rightChild = nullptr;
    };

    Node* findClosestParentOf(Node* n1, Node* n2) {
        vector<int> ancestVals;
        for (n1 = n1; n1 != nullptr; n1 = n1->parent) {
            ancestVals.push_back(n1->value);
        }

        for (n2 = n2; n2 != nullptr; n2 = n2->parent) {
            if (find(ancestVals.begin(), ancestVals.end(), n2->value) != ancestVals.end()) return n2;
        }
        return nullptr;
    }

    Node* searchNodeOf(Node* tree, int val) {
        if(tree->value == val) {
            return tree;
        }
        else {
            if (val < tree->value) return searchNodeOf(tree->leftChild, val);
            else return (searchNodeOf(tree->rightChild, val));
        }
        return nullptr;
    }

    Node* createNode (Node *_parent, int _value) {
        Node *node = new Node;
        node->parent = _parent;
        node->value = _value;

        return node;
    }

    Node* buildTree(Node *&parent, int val) {
        if (val < parent->value) {
            if (parent->leftChild == nullptr) parent->leftChild = createNode(parent, val);
            else buildTree(parent->leftChild, val);
        }
        else {
            if (parent->rightChild == nullptr) parent->rightChild = createNode(parent, val);
            else buildTree(parent->rightChild, val);
        }

        return parent;
    }

    Node* buildTree(vector<int> values) {   
        Node *base = createNode(nullptr, values[0]); 

        for (int i = 1; i < values.size(); i  ) {
            buildTree(base, values[i]);
        }
        return base;
    }

    vector<int> stringToInt(string str) {
        vector<int> vec;
        for (char* pch = strtok((char*)str.c_str(), "[ ,]"); pch != NULL; pch = strtok(NULL, "[ ,]")) {
            vec.push_back(stoi(pch));
        }

        return vec;
    }

    int BinarySearchTreeLCA(string strArr[], int length) { 
        vector<int> values = stringToInt(strArr[0]); //O(n)
        Node *tree = buildTree(values); //O(n^2)

        Node* n1 = searchNodeOf(tree, stoi(strArr[1])); //O(n)
        Node* n2 = searchNodeOf(tree, stoi(strArr[2])); //O(n)
        return findClosestParentOf(n1, n2)->value; //O(n)
    }

    int main(void) {
        string A[] = {"[3, 2, 1, 12, 4, 5, 13]", "5", "13"};
        int arrLength = sizeof(A) / sizeof(*A);
        cout << BinarySearchTreeLCA(A, arrLength);
        return 0;
    }

CodePudding user response：

The algorithm you have implemented is indeed not O(n). The buildTree function has in fact a O(nlogn) time complexity.

In order to solve this challenge with a linear time complexity, you could even omit building the binary search tree all together.

Instead, take these observations into consideration:

If a node is a common ancestor then it must have a value that lies between the two target values.
Not all values that are between the two target values are common ancestors.
Not all common ancestors are values between the two target values
There is actually only one value that lies between the two target values that is also a common ancestor. And this is the LCA.
All other values that are between the two target values are necessarily part of the subtree rooted in that LCA node.
As the nodes are given in preorder, the first value we find that lies between the two target values must be the LCA (for all of the above reasons)

The last point describes the linear algorithm you can implement, which is also a lot simpler than what you had done.