Skip to main content
Practice

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.


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.


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.


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.
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)

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.