Trees

Trees: Introduction & Terminology

A node of a tree is a single element of a tree. A tree is a collection of nodes. A node of a binary tree has a value and two pointers: left and right. A node of a non-binary tree has a value and any number of pointers.

Full: A Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children.

Perfect: A Perfect Binary Tree (PBT) is a tree with all leaf nodes at the same depth. All internal nodes have degree 2.

Complete: A Complete Binary Tree（CBT) is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

trees

Child: A child is a node that is a descendant of its parent.

Sibling: A sibling is a node that is a descendant of the same parent.

Leaf: A leaf is a node that has no children.

Binary Search Trees: Example

A binary search tree (BST) is a binary tree in which the value of each node is greater than the values in all of its left descendants and less than the values in all of its right descendants.

binary search tree

BST: Big O

The number of nodes in a binary tree with height h is O(2^h). Finding a node in a binary tree with height h is O(h). Therefore, the time complexity of a binary search tree is O(log n), where n is the number of nodes in the tree. The worst case is O(n) when the tree is completely unbalanced.

Comparison of the time complexity of a binary search tree with a linked list:

Insert(): O(1) in a linked list. In a binary search tree, Omega (best case) and Theta (average case) are both (log n). However, worst case is O(n) and Big O measures worst case.

Lookup(): O(n) in a linked list, O(log n) in a binary search tree.

Remove(): O(n) in a linked list, O(log n) in a binary search tree.

BST: Constructor

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

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

my_tree = BinarySearchTree()

print(my_tree.root)

The above code creates a empty tree.

BST: Insert

    def insert(self, value):
        new_node = Node(value)
        if self.root is None:
            self.root = new_node
            return True
        temp = self.root
        while (True):
            if new_node.value == temp.value:
                return False
            if new_node.value < temp.value:
                if temp.left is None:
                    temp.left = new_node
                    return True
                temp = temp.left
            else: 
                if temp.right is None:
                    temp.right = new_node
                    return True
                temp = temp.right

my_tree = BinarySearchTree()
my_tree.insert(2)
my_tree.insert(1)
my_tree.insert(3)

BST: Contains

    def contains(self, value):
        temp = self.root
        while (temp is not None):
            if value < temp.value:
                temp = temp.left
            elif value > temp.value:
                temp = temp.right
            else:
                return True
        return False

my_tree = BinarySearchTree()
my_tree.insert(47)
my_tree.insert(21)
my_tree.insert(76)
my_tree.insert(18)
my_tree.insert(27)
my_tree.insert(52)
my_tree.insert(82)

print(my_tree.contains(27))

print(my_tree.contains(17))

BST: Minimum Value

    def min_value_node(self, current_node):
        while (current_node.left is not None):
            current_node = current_node.left
        return current_node