Hierarchical

Binary Search Tree

A node-based binary tree structured for partitioned lookups and traversals.

What is Binary Search Tree?

A Binary Search Tree (BST) is a hierarchical, node-based data structure. For any given node, all elements stored in its left subtree must have a value less than the node's value, and all elements in its right subtree must have a value greater than the node's value. This recursive ordering property makes it highly efficient for binary partitioning search operations.

Key Characteristics:

  • Left subtree contains values less than parent
  • Right subtree contains values greater than parent
  • In-order traversal visits nodes in sorted order
  • Can degrade to a linked list (height O(n)) if unbalanced

Complexity Analysis

Avg Time Complexity: O(log n) Average Search/Insert, O(n) Worst case
Space Complexity: O(n) tree storage space
Best Case: O(1) (searching for value at root)
Worst Case: O(n) (fully skewed tree acting as linked list)

How it Works Step-by-Step

  1. Search: Compare target with node; traverse left if smaller, right if larger.
  2. Insert: Traverse down based on comparison, appending node at first empty child spot.
  3. Inorder Traversal: Traverse left subtree, visit node, traverse right subtree.
  4. Delete Node: If leaf, remove. If 1 child, bypass. If 2 children, swap with successor.

Code Implementation

Worked Trace Example

Searching for 25 in BST with root 50, left 30, right 70:
1. Compare 25 with root 50: 25 < 50, go left (node 30)
2. Compare 25 with node 30: 25 < 30, go left (node 20/leaf)
3. Compare 25 with leaf 20: 25 > 20, go right (NULL)
Result: 25 not found.