Binary search trees

Insert, search and inorder traversal, plus the case where a BST degrades to a list.

13 min read · Lesson 5 of 6 · Pro

The problem a BST solves

A sorted array gives O(log n) search but O(n) insert. A linked list gives O(1) insert but O(n) search. A binary search tree tries to get O(log n) for both.

The idea is one rule, applied at every node:

Everything in the left subtree is smaller than this node. Everything in the right subtree is bigger.

Because of that rule, at every node you throw away half the remaining tree. That is binary search, made out of pointers instead of index arithmetic.

The node

struct tnode {
    int key;
    struct tnode *left;
    struct tnode *right;
};

Insert and search

#include <stdio.h>
#include <stdlib.h>

The rest of this lesson is Pro

The free lessons of Data Structures in C finish what they start — read those first if you have not. This one goes further, and it is part of the paid half.

A pass opens the paid lessons of every course, the mock test papers and the company-wise series. It ends on its own date; nothing renews by itself.

Get a pass — from ₹29 for 7 days

Already bought one? Log in.