what is a binary search tree?
1 Like
Binary search tree is a special case of binary tree where every nodes follows a specific condition:
root.val > root.left.val and root.val < root.right.val
You can read a full code implementation here.
An important special kind of binary tree is the binary search tree (BST). In a BST, each node stores some information including a unique key value and perhaps some associated data. A binary tree is a BST iff, for every node n, in the tree:
- All keys in n’s left subtree are less than the key in n, and
- all keys in n’s right subtree are greater than the key in n.
Note: if duplicate keys are allowed, then nodes with values that are equal to the key in node n can be either in n’s left subtree or in its right subtree (but not both). In these notes, we will assume that duplicates are not allowed.