Skip to content

Binary Search Tree

A binary search tree (BST) is a specialized type of binary tree that maintains a specific order among its elements. In a BST, each node has at most two children, and the value of the left child is less than the value of the parent node, while the value of the right child is greater than the value of the parent node. This property allows for efficient searching, insertion, and deletion operations.

1
2
3
4
5
6
7
8
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.value)

Defining a tree

graph TD
    A[5]
    B[1]
    C[8]
    D[-1]
    E[3]
    F[7]
    G[9]

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
a = Node(5)
b = Node(1)
c = Node(8)
d = Node(-1)
e = Node(3)
f = Node(7)
g = Node(9)

a.left, a.right = b, c
b.left, b.right = d, e
c.left, c.right = f, g

Recursive in order traversal DFS (Depth First Search)

  • Time complexity: O(n) - Each node is visited once.
  • Space complexity: O(n) - In the worst case (a completely unbalanced tree).
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def in_order(node):
    if not node:
        return

    in_order(node.left)
    print(node)
    in_order(node.right)


in_order(a)

-1

1

3

5

7

8

9

Search for a value in a binary search tree

  • Time complexity: O(log n) - In a balanced BST, the height of the tree is log(n), so the search operation takes logarithmic time.
  • Space complexity: O(log n) - In a balanced BST, the height of the tree is log(n), so the space complexity is logarithmic due to the recursive call stack.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def search(node, target):
    if not node:
        return False

    if node.value == target:
        return True

    if target < node.value:
        return search(node.left, target)
    else:
        return search(node.right, target)


search(a, 8)

True