Validate Binary Search Tree

Verify if a binary tree is a valid Binary Search Tree (BST).

Lowest Common Ancestor of a BST

Find the lowest common ancestor (LCA) node of two given nodes in a BST.

Kth Smallest Element in a BST

Find the Kth smallest value (1-indexed) in a Binary Search Tree.

Serialize and Deserialize Binary Tree

Design an algorithm to serialize a binary tree into a string and deserialize back.

Non-Linear Data StructuresIntermediate LevelStudy Time: 25 mins

Binary Search Tree Data Structure

A Binary Search Tree (BST) is a hierarchical node structure where each parent node has at most two children. The left subtree contains values smaller than the parent, and the right subtree contains values larger, allowing efficient binary search scans.

Binary Search Tree (BST) Visualizer

BST initialized. Insert values to watch nodes traverse to their correct children slots.

Binary Search Tree Insertion Step-by-Step

Sample Input:BST Root: 50, Insert Value: 30, Insert Value: 70

Step 1

Compare Value with Root Node

Compare target 30 with root key 50. Since 30 < 50, branch to the left subtree.

Target: 30 < Root: 50 -> Move to Left Child

BST property enforces left < parent < right on all node levels.

Step 2

Attach Node at Null Leaf Position

If left child pointer is null, allocate new node(30) as left child of 50.

Root 50 -> Left Child: Node(30)

New key values are always inserted at leaf positions.

Step 3

Insert Larger Value (Insert 70)

Compare target 70 with root key 50. Since 70 > 50, branch to the right subtree.

Target: 70 > Root: 50 -> Right Child: Node(70)

Tree height remains 1, achieving O(log N) average depth.

Real-world analogy: Sorted Filing Cabinet

Root

Left Child

Right Child

Hover over items for details

Imagine walking into a library. To find book 50, you look at section 40. Since 50 > 40, you ignore everything to the left and search to the right.

Root= The top starting node of the tree hierarchy.
Left Child= Left subtree containing smaller key values.
Right Child= Right subtree containing larger key values.

Operations explained

Complexity analysis

Scenario Simulator: Dataset Size (N = 500)

Presets:

N = 10N = 10,000

Complexity Curve MapBinary Search Tree: O(log N) Tree Height Time

Hover curves to inspect classes

Time Steps (N=500)

~9 steps (Logarithmic)

O(log N) Tree Height Time

Space Footprint

O(N) Tree Nodes Space

Memory growth rate as N expands.

Performance Rank

Optimal Tier

Relative efficiency rating for large N.

Operation	Time Complexity	Space Complexity
Search	O(log N)	O(1)
Insertion	O(log N)	O(1)
Skewed Worst Case	O(N)	O(N)

Code implementations

class Node {
  constructor(val) {
    this.val = val;
    this.left = null; this.right = null;
  }
}
// Insert recursive check
function insert(root, 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;
}