Binary Search Tree

Concept

A BST is a binary tree where for every node, all values in the left subtree are smaller and all values in the right subtree are larger. This property enables O(log n) average search, insert, and delete. In-order traversal of a BST gives elements in sorted order.

When to Use

  • ▸Understanding how map/set work internally (red-black tree = balanced BST)
  • ▸Problems requiring ordered insertion, search, and deletion
  • ▸In-order traversal to get sorted output
  • ▸Interview/exam questions about tree data structures

Intuition

Think of a BST as a decision tree for searching. At each node, go left if your target is smaller, right if larger. It's like binary search but in tree form. Insert works the same way — walk down until you find an empty spot. In-order traversal (left, root, right) naturally visits nodes in sorted order because everything left is smaller and everything right is larger. In contests, use set/map instead of implementing BST from scratch.

Complexity

Time
O(log n) average, O(n) worst case (skewed tree)
Space
O(n)

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

struct Node{
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int val){
    if(!root) return new Node(val);
    if(val < root->val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

bool search(Node* root, int val){
    if(!root) return false;
    if(val == root->val) return true;
    if(val < root->val) return search(root->left, val);
    return search(root->right, val);
}

void inorder(Node* root){
    if(!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

void preorder(Node* root){
    if(!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

void postorder(Node* root){
    if(!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n;
    cin >> n;

    Node* root = nullptr;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        root = insert(root, x);
    }

    cout << "Inorder:   ";
    inorder(root);
    cout << "\n";

    cout << "Preorder:  ";
    preorder(root);
    cout << "\n";

    cout << "Postorder: ";
    postorder(root);
    cout << "\n";

    int q;
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        cout << (search(root, x) ? "YES" : "NO") << "\n";
    }

    return 0;
}

// Sample Input:
// 7
// 5 3 7 1 4 6 8
// 3
// 4
// 9
// 7
//
// Sample Output:
// Inorder:   1 3 4 5 6 7 8
// Preorder:  5 3 1 4 7 6 8
// Postorder: 1 4 3 6 8 7 5
// YES
// NO
// YES