What is a binary search tree?

Software Development
#1

what is a binary search tree?

1 Like
#2

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.

#3

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.