Tree

A tree is a hierarchical data structure that consists of nodes connected by edges. Each node contains a value and may have child nodes, forming a parent-child relationship. The topmost node is called the root, and nodes with no children are called leaves. Trees are used to represent various types of data, such as organizational structures, file systems, and hierarchical relationships.

Types of Trees

  1. Binary Tree: A tree where each node has at most two children, referred to as the left and right child.
  2. Binary Search Tree (BST): A binary tree where the value of each node is greater than the values of its left child and less than the values of its right child.
  3. AVL Tree: A self-balancing binary search tree where the difference in heights between the left and right subtrees cannot be more than one for any node.
  4. Red-Black Tree: A self-balancing binary search tree where each node has an extra bit for denoting the color of the node, either red or black, to ensure the tree remains balanced during insertions and deletions.
  5. B-Tree: A self-balancing tree data structure that maintains sorted data and allows for efficient insertion, deletion, and search operations. It is commonly used in databases and file systems.
  6. Trie: A tree-like data structure used to store a dynamic set of strings, where each node represents a common prefix of some strings. It is commonly used for autocomplete and spell-checking applications.
  7. Heap: A specialized tree-based data structure that satisfies the heap property, where the value of each node is greater than or equal to (in a max heap) or less than or equal to (in a min heap) the values of its children. Heaps are commonly used in priority queues and sorting algorithms.

Tree Traversal

Tree traversal refers to the process of visiting each node in a tree data structure in a specific order. The common tree traversal methods include:

  1. Pre-order Traversal: Visit the root node first, then recursively visit the left subtree, followed by the right subtree.
  2. In-order Traversal: Recursively visit the left subtree first, then visit the root node, followed by the right subtree. This traversal method is commonly used for binary search trees as it retrieves values in sorted order.
  3. Post-order Traversal: Recursively visit the left subtree first, then the right subtree, and finally visit the root node.
  4. Level-order Traversal: Visit the nodes level by level from left to right, starting from the root node.

Binary Tree Example

1
2
3
4
5
    A
   / \
  B   C
 / \   \
D   E   F
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

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

    def print_tree(self):
        def get_layer(node):
          if node is None:
            return 0
          else:
            left_depth = get_layer(node.left)
            right_depth = get_layer(node.right)
            return max(left_depth, right_depth) + 1

        layer = get_layer(self.root)

        queue = deque([(self.root, 1)])
        current_level = 1
        while queue:
          node, level = queue.popleft()
          if level > current_level:
            print()
            current_level += 1

          if node:
            print(f"{node.value:^{20*layer//2**(level-1)}}", end="")
          else:
            print(f"{"N":^{20*layer//2**(level-1)}}", end="")

          if level < layer:
            if node:
              queue.append((node.left, level + 1))
              queue.append((node.right, level + 1))
            else:
              queue.append((None, level + 1))
              queue.append((None, level + 1))

        print()

    # def insert(self, value):
    #     if self.root is None:
    #         self.root = TreeNode(value)
    #         self.size += 1
    #     else:
    #         self._insert_recursive(self.root, value)

    # def _insert_recursive(self, node, value):
    #     if value < node.value:
    #         if node.left is None:
    #             node.left = TreeNode(value)
    #             self.size += 1
    #         else:
    #             self._insert_recursive(node.left, value)
    #     elif value > node.value:
    #         if node.right is None:
    #             node.right = TreeNode(value)
    #             self.size += 1
    #         else:
    #             self._insert_recursive(node.right, value)
    #     else:
    #         # Value already exists in the tree, do nothing
    #         pass

    def search(self, value):
        return self._search_recursive(value)[0] is not None

    def _search_recursive(self, item):
      parent = None
      current = self.root
      while current:
        if item == current.data:
          break
        parent = current
        current = current.left if item < current.data else current.right
      return current, parent

    def insert(self, value):
      node, parent = self._search_recursive(value)
      if node is None:
        new_node = TreeNode(value)
        if parent is None:
          self.root = new_node
        elif value < parent.data:
          parent.left = new_node
        else:
          parent.right = new_node
        self._size += 1

    def __get_min(self,node):
      current = node
      while current.left:
        current = current.left
      return current

    def remove(self, item):
      current, parent = self._search_recursive(item)
      if not current:
        return

      if not current.left and not current.right:
        if parent:
          if parent.left == current:
            parent.left = None
          else:
            parent.right = None
        else:
          self.root = None

      elif not current.left or not current.right:
        child = current.left if current.left else current.right
        if parent:
          if parent.left == current:
            parent.left = child
          else:
            parent.right = child
        else:
          self.root = child

      else:
        successor = self.__get_min(current.right)
        successor_value = successor.data
        self.remove(successor_value)
        current.data = successor_value

      self._size -= 1

    def for_each(self, func, order="inorder"):
      match order:
        case "preorder":
          self._preorder(func)
        case "inorder":
          self._inorder(func)
        case "postorder":
          self._postorder(func)
        case "levelorder":
          self._levelorder(func)

    def _preorder(self, func):
      def _preorder_recursive(node):
        if node:
          func(node.data)
          _preorder_recursive(node.left)
          _preorder_recursive(node.right)

      _preorder_recursive(self.root)

    def _inorder(self, func):
      def _inorder_recursive(node):
        if node:
          _inorder_recursive(node.left)
          func(node.data)
          _inorder_recursive(node.right)
      
    _inorder_recursive(self.root)

    def _postorder(self, func):
      def _postorder_recursive(node):
        if node:
          _postorder_recursive(node.left)
          _postorder_recursive(node.right)
          func(node.data)

      _postorder_recursive(self.root)
  
    def _levelorder(self, func):
      queue = deque()
      queue.append(self.root)
      while queue:
        node = queue.popleft()
        if node:
          func(node.data)
          queue.append(node.left)
          queue.append(node.right)

    @property
    def size(self):
        return self._size

    def is_empty(self):
        return self.size == 0