Time complexity of binary search tree get_size method which i edited

Question

I am struggling to find time complexity of get_size method which i created in Binary Search Tree because of the fact that there is multiple recursion with multiple conditions.Here is code

`class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.right = right
        self.left = left

    def __str__(self):
        return str(self.data)

i created node class to stock data and then i created BST functions and it does work but problem is every functions time complexity should be log n in functions but i used if elif else and double recursion at the same time does it affect the run time if it does why if it doesn't why

class BST:
    def __init__(self):
        self.root = None

    def add(self, value, x=None):
        new_node = Node(value)
        if self.root is None:
            self.root = new_node
            return True
        if x is None:
            main_node = self.root
        else:
            main_node = x

        if value > main_node.data:
            if main_node.left is None:
                main_node.left = new_node
                return True
            else:
                return self.add(value, main_node.left)
        elif value == main_node.data:
            return False
        elif value < main_node.data:
            if main_node.right is None:
                main_node.right = new_node
                return True
            else:
                return self.add(value, main_node.right)

    def get_size(self, x=None):
        if self.root is None:
            return 0
        if x is None:
            main_node = self.root
        else:
            main_node = x
        if main_node.left is not None and main_node.right is not None:
            return 1 + self.get_size(main_node.left) + self.get_size(main_node.right)
        elif main_node.left is None and main_node.right is None:
            return 1
        else:
            if main_node.left is not None:
                return 1 + self.get_size(main_node.left)
            else:
                return 1 + self.get_size(main_node.right)`

Answer 1

To determine the complexity, it helps to break your function apart and analyze the different parts separately.

Starting with the base cases, your complexity is O(1).

if self.root is None:
    return 0

elif main_node.left is None and main_node.right is None:
    return 1

However, as your start recursing, those base cases will add up. Let's look at one of the recursive calls:

if main_node.left is not None and main_node.right is not None:
    return 1 + self.get_size(main_node.left) + self.get_size(main_node.right)

In the simplest tree where main_node's left and right children are both leaves, then these 2 calls to get_size() will not recurse any farther, resulting in two O(1) operations. However, if either of the nodes have children, then we will make additional calls to get_size(), making get_size() something greater than O(1). If the left child had children, but those children are leaves, then we will again call get_size() two more times, each being an O(1) call.

If we repeat this analysis for every possible if/else statement in the function, we will see that for each child that exists, we will call get_size() for it once and only once. Therefore, our overall complexity is O(n).