← Back to DSA Course | Chapter 11: Trees | Lesson 4 of 10

Binary Search Tree

In this page:

  1. BST Rule
  2. BST Search Idea
  3. BST Inorder
  4. BST Minimum and Maximum
  5. BST Practice

BST Rule

A binary search tree (BST) is a binary tree with an ordering rule: for every node, all values in its left subtree are smaller than the node's value, and all values in its right subtree are larger. This rule is what makes fast searching possible.

Example: BST Rule

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "left(" << root.left->val << ") < root(" << root.val << ") < right(" << root.right->val << ")" << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("left(" + root.left.val + ") < root(" + root.val + ") < right(" + root.right.val + ")");
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

root = Node(5)
root.left = Node(3); root.right = Node(8)
print(f"left({root.left.val}) < root({root.val}) < right({root.right.val})")
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("left(%d) < root(%d) < right(%d)\n", root.left->val, root.val, root.right->val);
    return 0;
}

BST Search Idea

Because of the ordering rule, searching a BST only ever needs to follow one path from the root: at each node, compare the target to the current value and move left or right accordingly, discarding the other subtree entirely without checking it.

Example: BST Search Idea

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* search(Node* n, int target) {
    if (!n || n->val == target) return n;
    return target < n->val ? search(n->left, target) : search(n->right, target);
}
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    Node* found = search(&root, 3);
    cout << (found ? "Found" : "Not found") << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static Node search(Node n, int target) {
        if (n == null || n.val == target) return n;
        return target < n.val ? search(n.left, target) : search(n.right, target);
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        Node found = search(root, 3);
        System.out.println(found != null ? "Found" : "Not found");
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def search(n, target):
    if n is None or n.val == target:
        return n
    return search(n.left, target) if target < n.val else search(n.right, target)

root = Node(5)
root.left = Node(3); root.right = Node(8)
print("Found" if search(root, 3) else "Not found")
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
struct Node* search(struct Node* n, int target) {
    if (!n || n->val == target) return n;
    return target < n->val ? search(n->left, target) : search(n->right, target);
}
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    struct Node* found = search(&root, 3);
    printf("%s\n", found ? "Found" : "Not found");
    return 0;
}

BST Inorder

Running an inorder traversal on a BST — left subtree, node, right subtree — visits every value in fully sorted order, which is a direct consequence of the BST ordering rule and one of the most useful properties of the structure.

Example: BST Inorder

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
void inorder(Node* n) { if(!n) return; inorder(n->left); cout<<n->val<<" "; inorder(n->right); }
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    inorder(&root);
    cout << "(sorted order)" << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static void inorder(Node n) { if(n==null) return; inorder(n.left); System.out.print(n.val+" "); inorder(n.right); }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        inorder(root);
        System.out.println("(sorted order)");
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def inorder(n):
    if n is None: return
    inorder(n.left); print(n.val, end=" "); inorder(n.right)

root = Node(5)
root.left = Node(3); root.right = Node(8)
inorder(root)
print("(sorted order)")
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
void inorder(struct Node* n) { if(!n) return; inorder(n->left); printf("%d ",n->val); inorder(n->right); }
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    inorder(&root);
    printf("(sorted order)\n");
    return 0;
}

BST Minimum and Maximum

The minimum value in a BST is always found by following left children as far as possible from the root, and the maximum is always found by following right children as far as possible — no comparisons against the node values are even needed.

Example: BST Minimum and Maximum

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* findMin(Node* n) { while (n->left) n = n->left; return n; }
Node* findMax(Node* n) { while (n->right) n = n->right; return n; }
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "Min: " << findMin(&root)->val << ", Max: " << findMax(&root)->val << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static Node findMin(Node n) { while (n.left != null) n = n.left; return n; }
    static Node findMax(Node n) { while (n.right != null) n = n.right; return n; }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("Min: " + findMin(root).val + ", Max: " + findMax(root).val);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def find_min(n):
    while n.left: n = n.left
    return n

def find_max(n):
    while n.right: n = n.right
    return n

root = Node(5)
root.left = Node(3); root.right = Node(8)
print("Min:", find_min(root).val, ", Max:", find_max(root).val)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
struct Node* findMin(struct Node* n) { while (n->left) n = n->left; return n; }
struct Node* findMax(struct Node* n) { while (n->right) n = n->right; return n; }
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("Min: %d, Max: %d\n", findMin(&root)->val, findMax(&root)->val);
    return 0;
}

BST Practice

BSTs are the right choice whenever you need both fast lookups and the ability to retrieve data in sorted order — the tradeoff is that a poorly balanced BST (built from already-sorted input, for example) degrades toward a plain linked list in the worst case.

Example: BST Practice

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int height(Node* n) {
    if (!n) return 0;
    int l = height(n->left), r = height(n->right);
    return 1 + (l > r ? l : r);
}
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "Balanced BST height: " << height(&root) << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static int height(Node n) {
        if (n == null) return 0;
        return 1 + Math.max(height(n.left), height(n.right));
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("Balanced BST height: " + height(root));
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def height(n):
    if n is None: return 0
    return 1 + max(height(n.left), height(n.right))

root = Node(5)
root.left = Node(3); root.right = Node(8)
print("Balanced BST height:", height(root))
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int height(struct Node* n) {
    if (!n) return 0;
    int l = height(n->left), r = height(n->right);
    return 1 + (l > r ? l : r);
}
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("Balanced BST height: %d\n", height(&root));
    return 0;
}
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Level Order Traversal BFS Next Lesson → BST Insert Delete Search

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.