DSA 39: Binary Search Trees - Rules [Part 2]

1. Binary Trees and Binary Search Trees

1.1 Binary Tree

Is a tree in which each node has either:

• zero,
• one, or
• two children.

1.2 Binary Search Tree

Is a binary tree abiding to the following rules:

• Each node can have at most
  • one left child and
  • one right child.
• A node’s left descendants can only contain have:
  • values that are less than the node itself.
• A node’s right descendants can only contain have:
  • values that are greater than the node itself.

2. Basic TreeNode Implementation

class TreeNode:
    def __init__(self, data: int, left=None, right=None):
        self.data        = data
        self.left_child  = left
        self.right_child = right

3. Basic Binary Search Tree Implementation

node1 = TreeNode(25)
node2 = TreeNode(75)
root = TreeNode(50, node1, node2)