BST: Validate BST

👩‍💻 문제

You are tasked with writing a method called is_valid_bst in the BinarySearchTree class that checks whether a binary search tree is a valid binary search tree.

Your method should use the dfs_in_order method to get the node values of the binary search tree in ascending order, and then check whether each node value is greater than the previous node value.

If the node values are not sorted in ascending order, the method should return False, indicating that the binary search tree is not valid.

If all node values are sorted in ascending order, the method should return True, indicating that the binary search tree is a valid binary search tree.

 

💡 내 첫 풀이 : O(nlogn)

def is_valid_bst(self):
        bst_list = self.dfs_in_order()
        if bst_list == sorted(bst_list):
            return True
        else:
            return False

 

* Time Complexity : O(nlogn)
self.dfs_in_order() : 각 노드를 쭉 순회하기 때문에 O(n)

sorted(bst_list) : O(nlogn) 이 들어간다

bst_list == sorted(bst_list) 비교하는 것도, 각 원소를 순회하면서 비교하므로 O(n)

최대로 큰 애가 O(nlogn) 이므로 이게 dominate

 

 

💡 더 나은 정답 풀이 : O(n)

def is_valid_bst(self):
        node_values = self.dfs_in_order()
        for i in range(1, len(node_values)):
            if node_values[i] <= node_values[i-1]:
                return False
        return True

일단 dfs_in_order : O(n)

for loop : O(n)

O(2n) 정도가 들어가기 때문에 결과적으로는 O(n) ! 

굳이 모든 리스트 원소를 비교하지 않고, 바로 앞과 뒤 애만 비교해서, 앞에가 더 커버리면 바로 끝내버리면 되는거니까!

 

 

🥳 배운점

좀 더 효율적으로 코드 짜는 법

그래고 sorted() 내장 함수는 O(nlogn)의 Time complexity를 가진다는 것