Trees & BST

What Is a Tree?

A Tree is a hierarchical data structure made up of nodes.
Each node stores data and links (called edges) to its child nodes.

        A

       / \

      B   C

     / \

    D   E

• Root: The topmost node (A)

• Parent/Child: Relationship between connected nodes (A → B, A → C)

• Leaf: Node with no children (D, E, C)

• Edge: Connection between two nodes

• Height: Longest path from root to any leaf

Unlike arrays or linked lists, which are linear, trees are non-linear, allowing efficient hierarchical storage.

Types of Trees

There are many types of trees, but in DSA we mostly work with:

1. Binary Tree – Each node has at most two children (left and right).

2. Binary Search Tree (BST) – A special binary tree that maintains sorted order.

3. AVL Tree, Red-Black Tree – Self-balancing versions of BST.

4. N-ary Tree, Trie, Segment Tree, etc. – Used in more complex problems.

Binary Tree Basics

Binary Tree

In Python:

class Node:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

Example:

root = Node(10)

root.left = Node(5)

root.right = Node(20)

root.left.left = Node(3)

root.left.right = Node(7)

This form:

        10

       /  \

      5    20

     / \

    3   7

Tree Traversals

Tree traversal means visiting each node in a specific order.

Inorder (Left → Root → Right)

def inorder(root):

    if root:

        inorder(root.left)

        print(root.data, end=" ")

        inorder(root.right)

Preorder (Root → Left → Right)

def preorder(root):

    if root:

        print(root.data, end=" ")

        preorder(root.left)

        preorder(root.right)

Level Order (Breadth-First Search)

from collections import deque

def level_order(root):

    if not root:

        return

    q = deque([root])

    while q:

        node = q.popleft()

        print(node.data, end=" ")

        if node.left:

            q.append(node.left)

        if node.right:

            q.append(node.right)

Binary Search Tree (BST)

A Binary Search Tree (BST) is a special kind of binary tree that maintains sorted order:

Left child < Parent < Right child

This property makes searching and insertion efficient — usually O(log n) time. 

Creating a BST

class BST:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

    def insert(self, value):

        if value < self.data:

            if self.left:

                self.left.insert(value)

            else:

                self.left = BST(value)

        elif value > self.data:

            if self.right:

                self.right.insert(value)

            else:

                self.right = BST(value)

Searching in a BST

def search(root, key):

    if root is None or root.data == key:

        return root

    if key < root.data:

        return search(root.left, key)

    return search(root.right, key)

Finding Minimum and Maximum

def find_min(root):

    while root.left:

        root = root.left

    return root.data

def find_max(root):

    while root.right:

        root = root.right

    return root.data

Operation	Average Case	Worst Case (Unbalanced)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Traversal	O(n)	O(n)