Binary Tree Using Python

A binary tree is a data structure that consists of nodes that have a maximum of two children. It is called a binary tree because each node has at most two children.

Here is a basic implementation of a binary tree in Python:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = Noneclass BinaryTree:
    def __init__(self):
        self.root = Nonedef insert(self, value):
        new_node = Node(value)
        if self.root == None:
            self.root = new_node
        else:
            current = self.root
            while True:
                if value < current.value:
                    if current.left:
                        current = current.left
                    else:
                        current.left = new_node
                        breakelse:
                    if current.right:
                        current = current.right
                    else:
                        current.right = new_node
                        breakdef search(self, value):
        current = self.root
        while current:
            if value == current.value:
                return Trueelif value < current.value:
                current = current.left
            else:
                current = current.right
        return False

The above implementation of binary tree has insert and search methods. The insert method takes a value as input and adds it to the tree in the correct position. The search method takes a value as input and returns a Boolean value indicating whether the value is present in the tree or not.

Time complexity of insert and search in binary tree:

• The time complexity of insert and search is O(log n) on average, where n is the number of nodes in the tree. In the worst case, it could be O(n) if the tree is not balanced.

Space complexity of binary tree:

• The space complexity of a binary tree is O(n), where n is the number of nodes in the tree. This is because each node in the tree requires a fixed amount of memory to store its value and pointers to its children.