Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Binary Search Tree
DSA

Binary Search Tree

Learn BST properties, search, insertion, deletion, traversal, and common interview problems.

BST is a binary tree where left < root < right for all nodes. This ordering property enables O(log n) search.

Its core advantage:

BST search eliminates half the tree at each step — O(h) time, h = height.

Focus on recognizing:

“Sorted property” + “Left < root < right” + “Binary search” = BST

Pattern Table

PatternTypical QuestionsTrigger
Search / InsertFind or add nodeCompare value and go left/right
Validate BSTIs it a valid BST?Range check (min, max)
Kth SmallestFind Kth smallest elementInorder traversal

Mental Trigger

Compare value → Go left if smaller, right if larger → O(h).

1. Generic Java BST Template (Base)

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public TreeNode search(TreeNode root, int key) {
    if (root == null || root.val == key)
        return root;

    if (key < root.val)
        return search(root.left, key);

    return search(root.right, key);
}
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def search(root, key):
    if root is None or root.val == key:
        return root

    if key < root.val:
        return search(root.left, key)

    return search(root.right, key)
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* search(TreeNode* root, int key) {
    if (root == nullptr || root->val == key)
        return root;

    if (key < root->val)
        return search(root->left, key);

    return search(root->right, key);
}
class TreeNode {
  constructor(x) {
    this.val = x;
    this.left = null;
    this.right = null;
  }
}

function search(root, key) {
  if (root === null || root.val === key)
    return root;

  if (key < root.val)
    return search(root.left, key);

  return search(root.right, key);
}

Everything else in BST is just a modification of this template.

Pattern 1: Insert into BST

Comparisons walk you down; the first empty slot is your leaf. Press ▶ to animate.

BST Insert

Insert a value into a BST by walking comparisons and attaching a leaf.

Start at the root; go left if smaller, right if larger, until an empty child slot is found, then attach the new node there. Inserts are always leaves, so plain BST insert needs no rebalancing.

TREE VISUALIZER
Steps –
5030702045
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        walk from root:
                      
                        2
                          val < node → go left
                      
                        3
                          val > node → go right
                      
                        4
                        attach at empty slot

Java Code

public TreeNode insert(TreeNode root, int val) {
    if (root == null)
        return new TreeNode(val);

    if (val < root.val)
        root.left = insert(root.left, val);
    else if (val > root.val)
        root.right = insert(root.right, val);

    return root;
}
def insert(root, val):
    if root is None:
        return TreeNode(val)

    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)

    return root
TreeNode* insert(TreeNode* root, int val) {
    if (root == nullptr)
        return new TreeNode(val);

    if (val < root->val)
        root->left = insert(root->left, val);
    else if (val > root->val)
        root->right = insert(root->right, val);

    return root;
}
function insert(root, val) {
  if (root === null)
    return new TreeNode(val);

  if (val < root.val)
    root.left = insert(root.left, val);
  else if (val > root.val)
    root.right = insert(root.right, val);

  return root;
}

What Changed from the Base Template?

Create node on null

Base:

if (root == null || root.val == key) return root;

Changed:

if (root == null) return new TreeNode(val);

because insertion creates a new node when it reaches a null position.

Insert = Search + Create node at null position.

Pattern 2: Validate BST

Min/max bounds travel down the tree — local checks aren’t enough. Press ▶ to animate.

Validate Binary Search Tree

Confirm a tree is a BST where every node lies strictly between inherited min/max bounds.

Recurse with a (lo, hi) window; each node must be inside its ancestors' bounds. A naive 'left<me<right' check misses violations that appear only against higher ancestors — bounds must travel down.

TREE VISUALIZER
Steps –
10515613
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        valid(node, lo, hi):
                      
                        2
                          node in (lo, hi)?
                      
                        3
                          left  = valid(node.l, lo, node.val)
                      
                        4
                          right = valid(node.r, node.val, hi)

Java Code

public boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}

private boolean validate(TreeNode root, Integer min, Integer max) {
    if (root == null) return true;

    if ((min != null && root.val <= min) ||
        (max != null && root.val >= max))
        return false;

    return validate(root.left, min, root.val)
        && validate(root.right, root.val, max);
}
def is_valid_bst(root):
    return validate(root, None, None)

def validate(root, min_val, max_val):
    if root is None:
        return True

    if (min_val is not None and root.val <= min_val) or \
       (max_val is not None and root.val >= max_val):
        return False

    return validate(root.left, min_val, root.val) and \
           validate(root.right, root.val, max_val)
bool isValidBST(TreeNode* root) {
    return validate(root, LLONG_MIN, LLONG_MAX);
}

bool validate(TreeNode* root, long long minVal, long long maxVal) {
    if (root == nullptr) return true;

    if (root->val <= minVal || root->val >= maxVal)
        return false;

    return validate(root->left, minVal, root->val)
        && validate(root->right, root->val, maxVal);
}
function isValidBST(root) {
  return validate(root, null, null);
}

function validate(root, min, max) {
  if (root === null) return true;

  if ((min !== null && root.val <= min) ||
      (max !== null && root.val >= max))
    return false;

  return validate(root.left, min, root.val)
    && validate(root.right, root.val, max);
}

What Changed from the Base Template?

Range tracking

Base:

// just search for value

Changed:

Integer min, Integer max

because validation requires that all nodes in the left subtree are < root and all in the right subtree are > root.

Recursive range narrowing

Added:

validate(root.left, min, root.val)   // upper bound = current root
validate(root.right, root.val, max)  // lower bound = current root

to propagate the allowed range as we descend.

Validate BST = DFS with (min, max) range — left narrows max, right narrows min.

Pattern 3: Kth Smallest Element

Inorder = sorted order; just count pops until k. Press ▶ to animate.

Kth Smallest In A BST

Find the k-th smallest element of a BST using iterative inorder.

Because inorder of a BST is sorted, push the left spine, pop-visit while counting, and stop when the counter reaches k. Each pop hands back the next-larger node.

TREE VISUALIZER
Steps –
53816
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        stack = []; cur = root
                      
                        2
                        while stack or cur:
                      
                        3
                          push left spine; cur = left
                      
                        4
                          cur = pop(); count++
                      
                        5
                          if count == k → answer
                      
                        6
                          cur = cur.right

Java Code

public int kthSmallest(TreeNode root, int k) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;

    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }

        curr = stack.pop();
        k--;

        if (k == 0) return curr.val;

        curr = curr.right;
    }

    return -1;
}
def kth_smallest(root, k):
    stack = []
    curr = root

    while curr is not None or stack:
        while curr is not None:
            stack.append(curr)
            curr = curr.left

        curr = stack.pop()
        k -= 1

        if k == 0:
            return curr.val

        curr = curr.right

    return -1
int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    TreeNode* curr = root;

    while (curr != nullptr || !st.empty()) {
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }

        curr = st.top();
        st.pop();
        k--;

        if (k == 0) return curr->val;

        curr = curr->right;
    }

    return -1;
}
function kthSmallest(root, k) {
  const stack = [];
  let curr = root;

  while (curr !== null || stack.length > 0) {
    while (curr !== null) {
      stack.push(curr);
      curr = curr.left;
    }

    curr = stack.pop();
    k--;

    if (k === 0) return curr.val;

    curr = curr.right;
  }

  return -1;
}

What Changed from the Base Template?

Count during inorder

Base:

// collect all or search for value

Changed:

k--;
if (k == 0) return curr.val;

because inorder traversal of BST produces sorted order — the Kth visited node is the Kth smallest.

Kth Smallest = Inorder traversal + Stop at Kth visited node.

BST Pattern Evolution

BST Search (compare + go left/right)
    ↓
Insert
    (+ create node at null position)
    ↓
Validate
    (+ range bounds narrowing)
    ↓
Kth Smallest
    (+ inorder traversal + count)

Common Mistakes

Not handling duplicates in validation.

root.val <= min and root.val >= max — BST typically excludes duplicates.

Forgetting BST property in insertion.

Equal values: skip or handle based on problem specification.

Using recursion for large unbalanced trees.

Stack overflow possible — use iterative stack or Morris traversal.

Recognition Cheat Sheet

If you see…Think…
Sorted tree propertyBST
Insert into BSTSearch + create
Validate BSTRange check (min, max)
Kth smallest/largestInorder + count
Search in BSTCompare + go left/right

My Private Notes

Notes are auto-saved locally to this device.