A binary search tree (BST) is a binary tree with one extra rule, true at every node: every value in its left subtree is smaller than the node, and every value in its right subtree is bigger. That single rule is what makes a BST useful — at any node, one comparison tells you which half of the tree a value must be in, so the other half can be skipped without looking at it.
It's not enough for each node to be bigger than its left child and smaller than its right child. Every value below on the left must be smaller — grandchildren included. In the tree below, 9 is a fine right child of 3, but it sits inside 8's left subtree, where everything must be smaller than 8. Searching for 9 would go right at 8 and never find it.
Members only · free account
The rest of this lesson, with 5 more sections, a dry-run simulator and code in JavaScript, Python, Java and C++, opens with a free account.
Was this helpful?
Not ready yet? The Arrays course is free to read, no account needed.
In the rest of this lesson