V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Binary Search Tree

Hierarchical search guided by an ordering invariant

Every comparison chooses one subtree

In a binary search tree (BST), every value in a node's left subtree is smaller and every value in its right subtree is larger. Searching compares the target with the current node and discards one entire subtree. Inorder traversal visits the values in ascending order.

Try it
50
30
70
20
40
60
80

Enter an integer from 1 to 99, then insert it to trace its path.

Search and insertion take O(h), where h is the tree height. A balanced tree has h = O(log n), but ordinary BST insertion does not guarantee that shape.

Shape controls performance

Inserting already sorted values can create a one-sided chain with height n. AVL trees and red-black trees rotate nodes to keep their height logarithmic while preserving the same ordering invariant. Compare the two shapes using exactly the same seven values.

Try it
1234567

Height 7 levels · worst-case search 7 comparisons(O(n), like a linked list)

Both trees contain 1 through 7. Search for 7 and compare the path lengths.

Invariant: ordering determines correctness; balance determines the performance bound. A valid but skewed BST still returns correct answers, only more slowly.

A heap keeps a weaker parent-child order to make the minimum or maximum easy to remove, while a BST supports ordered search.