Binary Search Tree

Ordering invariant: left is smaller, right is larger. In-order traversal yields sorted output.

Newinterview weight 6515 problems2 visualisers

mastery

Attempts logged

Predicted success on the next one

33%

Solved here

0 / 15

What you actually need to hold in your head

Search, insert and delete in O(h)
In-order gives a sorted sequence
Validate with min and max bounds, not just children
Balance is what keeps the height logarithmic

Comfortable with these first

Trees18%Binary Search18%

Next in the path

Heap / Priority Queue

Watch it run

Step through the algorithm before you write it.

BST Insert & SearchM

Left is smaller, right is larger. That one rule turns search, insert and delete into a single walk down the tree.

O(h), which is O(log n) when balanced

Validate a BSTM

Checking a node against its direct children is not enough. Pass an allowed range down the tree and narrow it at each step.

O(n)

Patterns in this topic

The trigger phrases are what you are training yourself to notice.

BST OrderingO(h) for search, O(n) for traversal

Use the ordering invariant to skip entire subtrees, and remember that in-order traversal emits sorted values.

validate BSTkth smallest