lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

pythonIntroAlgorithms2Chapter2Title

lesson12Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

pythonIntroAlgorithms2Chapter1Title

pythonIntroAlgorithms2Chapter3Title

pythonIntroAlgorithms2Chapter4Title

class TreeNode:
 def __init__(self, key):
 self.key = key
 self.left = None
 self.right = None


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

 def insert(self, key):
 # Insert new key into the tree
 if self.root is None:
 self.root = TreeNode(key)
 else:
 self._insert_recursive(self.root, key)

 def _insert_recursive(self, node, key):
 if key < node.key:
 if node.left is None:
 node.left = TreeNode(key)
 else:
 self._insert_recursive(node.left, key)
 elif key > node.key:
 if node.right is None:
 node.right = TreeNode(key)
 else:
 self._insert_recursive(node.right, key)

 def search(self, key):
 # Search for the key in the tree
 return self._search_recursive(self.root, key)

 def _search_recursive(self, node, key):
 if node is None or node.key == key:
 return True
 if key < node.key:
 return self._search_recursive(node.left, key)
 return self._search_recursive(node.right, key)

 def preorder_traversal(self):
 # Traverse all nodes in preorder
 result = []
 self._preorder_traversal_recursive(self.root, result)
 return result

 def _preorder_traversal_recursive(self, node, result):
 if node is not None:
 result.append(node.key) # Visit node
 self._preorder_traversal_recursive(node.left, result) # Visit left child
 self._preorder_traversal_recursive(node.right, result) # Visit right child


bst = BinarySearchTree()

bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(8)
bst.insert(3)
bst.insert(7)
bst.insert(18)

print(bst.preorder_traversal())
print("Search for 18:", bst.search(18))

# Tree Implementation Techniques

## 1. Defining the Tree Node Class

- A tree is a hierarchical data structure consisting of nodes connected through parent-child relationships.

- The `TreeNode` class contains each node's data and references to its left and right children.

 

```python title="Define Tree Node Class"
class TreeNode:
 def __init__(self, key):
 self.key = key
 self.left = None
 self.right = None
```

 

## 2. Defining the Binary Search Tree Class

- A binary search tree is a type of tree where each node has at most two children, and the left child is smaller than the parent node, while the right child is greater.

- The `BinarySearchTree` class stores the root node of the tree.

 

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

 

## 3. Key Insertion Method

- The `insert` method adds a new key to the tree.

- During insertion, nodes are placed in appropriate positions to maintain the properties of the binary search tree.

 

```python title="Key Insertion Method Example"
def insert(self, key):
 if self.root is None:
 self.root = TreeNode(key)
 else:
 self._insert_recursive(self.root, key)

def _insert_recursive(self, node, key):
 if key < node.key:
 if node.left is None:
 node.left = TreeNode(key)
 else:
 self._insert_recursive(node.left, key)
 elif key > node.key:
 if node.right is None:
 node.right = TreeNode(key)
 else:
 self._insert_recursive(node.right, key)
```

 

## 4. Creating and Using a Binary Search Tree Object

- Create an instance of the `BinarySearchTree` class and insert keys to form the tree.

```python title="Creating and Using a Binary Search Tree Object Example"
# Create a binary search tree object
bst = BinarySearchTree()

# Insert keys
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
```

Tree Implementation Techniques