1"""
2Unbalanced Binary Search Tree (UBST) - Hierarchical Data Structure
3
4An unbalanced binary search tree is a node-based data structure where each
5node has at most two children (left and right). For every node, all values
6in its left subtree are smaller, and all values in its right subtree are
7larger. This ordering property enables efficient searching.
8
9Note: This tree does NOT self-balance. In the worst case (e.g., inserting
10sorted data), the tree degenerates into a linked list.
11
12Time Complexity:
13 - add: O(h)
14 - search: O(h)
15 - delete: O(h)
16 - find_successor: O(h)
17 - traverse: O(n)
18
19Space Complexity:
20 - add: O(h) - recursion stack
21 - search: O(h) - recursion stack
22 - delete: O(h) - recursion stack
23 - find_successor: O(h) where h = height (O(n) worst case)
24 - traverse: O(n) - recursion stack
25"""
26
27from enum import Enum
28
29
30class TreeNode:
31 """A single node in the binary search tree."""
32
33 def __init__(self, val):
34 self.val = val
35 self.left = None
36 self.right = None
37
38 def __str__(self):
39 return str(self.val)
40
41 def __repr__(self):
42 return str(self.val)
43
44
45class UbstTree:
46 """
47 Unbalanced Binary Search Tree implementation.
48
49 Provides operations for adding, searching, deleting nodes,
50 finding successors, and traversing the tree in different orders.
51 """
52
53 def __init__(self, val):
54 """Initialize the tree with a root value."""
55 self.root = TreeNode(val)
56
57 def __contains__(self, val):
58 """Allow 'val in tree' syntax."""
59 return self.search(val) is not None
60
61 def add(self, val):
62 """Add a value to the tree. Duplicates are ignored."""
63
64 def _add(val, cur_node: TreeNode):
65 if cur_node is None:
66 return TreeNode(val)
67
68 if cur_node.val == val:
69 return cur_node
70 elif val < cur_node.val:
71 cur_node.left = _add(val, cur_node.left)
72 elif cur_node.val < val:
73 cur_node.right = _add(val, cur_node.right)
74
75 return cur_node
76
77 self.root = _add(val, self.root)
78
79 def search(self, val):
80 """
81 Search for a value in the tree.
82 Returns the node if found, None otherwise.
83 """
84
85 def _search(val, cur_node: TreeNode):
86 if cur_node is None:
87 return None
88
89 if val < cur_node.val:
90 return _search(val, cur_node.left)
91 elif cur_node.val < val:
92 return _search(val, cur_node.right)
93 else:
94 return cur_node
95
96 return _search(val, self.root)
97
98 def delete(self, val):
99 """
100 Delete a value from the tree.
101 Handles three cases: no children, one child, two children.
102 """
103 if not self.root:
104 return
105
106 def _delete_node(cur_node: TreeNode, val_to_delete):
107 if cur_node is None:
108 return None
109 if val_to_delete < cur_node.val:
110 cur_node.left = _delete_node(cur_node.left, val_to_delete)
111 return cur_node
112 elif cur_node.val < val_to_delete:
113 cur_node.right = _delete_node(cur_node.right, val_to_delete)
114 return cur_node
115 else: # cur_node.val == val_to_delete
116 if cur_node.left and cur_node.right:
117 # 2 children
118 successor = self.find_successor(cur_node)
119 cur_node.val = successor.val
120 cur_node.right = _delete_node(cur_node.right, successor.val)
121 return cur_node
122 elif cur_node.left:
123 # only left child
124 return cur_node.left
125 elif cur_node.right:
126 # only right child
127 return cur_node.right
128 else:
129 # no children
130 return None
131
132 self.root = _delete_node(self.root, val)
133
134 def find_successor(self, node: TreeNode):
135 """
136 Find the in-order successor of a node.
137 If node has right subtree: successor is the leftmost node in right subtree.
138 Otherwise: successor is the first ancestor where node is in left subtree.
139 """
140 if node.right:
141 # find leftmost child of right subtree
142 leftmost_child_right_subtree = node.right
143 while leftmost_child_right_subtree.left:
144 leftmost_child_right_subtree = leftmost_child_right_subtree.left
145 return leftmost_child_right_subtree
146 else:
147 # find the first ancestor for which the node is in the left subtree
148 successor = None
149 current = self.root
150 while current:
151 if current.val < node.val:
152 current = current.right
153 elif node.val < current.val:
154 successor = current
155 current = current.left
156 else:
157 break
158 return successor
159
160 class TraverseOrder(Enum):
161 """Enumeration of tree traversal orders."""
162
163 preorder = 1
164 inorder = 2
165 postorder = 3
166
167 def traverse(self, type: TraverseOrder):
168 """
169 Traverse the tree in the specified order.
170 Returns a list of values.
171 """
172 arr = []
173
174 def _postorder(root: TreeNode):
175 if not root:
176 return
177 _postorder(root.left)
178 _postorder(root.right)
179 arr.append(root.val)
180
181 def _inorder(root: TreeNode):
182 if not root:
183 return
184 _inorder(root.left)
185 arr.append(root.val)
186 _inorder(root.right)
187
188 def _preorder(root: TreeNode):
189 if not root:
190 return
191 arr.append(root.val)
192 _preorder(root.left)
193 _preorder(root.right)
194
195 if type == UbstTree.TraverseOrder.preorder:
196 _preorder(self.root)
197 elif type == UbstTree.TraverseOrder.postorder:
198 _postorder(self.root)
199 elif type == UbstTree.TraverseOrder.inorder:
200 _inorder(self.root)
201 else:
202 raise TypeError("Invalid traverse order passed.")
203
204 return arr
205
206
207# Example usage:
208if __name__ == "__main__":
209 tree = UbstTree(10)
210 tree.add(5)
211 tree.add(15)
212 tree.add(3)
213 tree.add(7)
214 tree.add(12)
215 tree.add(18)
216
217 # Traverse in different orders
218 print(tree.traverse(UbstTree.TraverseOrder.preorder)) # [10, 5, 3, 7, 15, 12, 18]
219 print(tree.traverse(UbstTree.TraverseOrder.inorder)) # [3, 5, 7, 10, 12, 15, 18]
220 print(tree.traverse(UbstTree.TraverseOrder.postorder)) # [3, 7, 5, 12, 18, 15, 10]
221
222 # Search
223 print(tree.search(12)) # TreeNode with val=12
224 print(7 in tree) # True
225
226 # Delete nodes
227 tree.delete(7) # no children
228 tree.delete(10) # 2 children
229 tree.delete(18) # 1 child
230 tree.delete(100) # not in tree
231