[prev] 15 [next]

Binary Search Trees

Binary search trees (or BSTs) have the characteristic properties
  • each node is the root of 0, 1 or 2 subtrees
  • all values in any left subtree are less than root
  • all values in any right subtree are greater than root
  • these properties applies over all nodes in the tree
perfectly balanced trees have the properties
  • #nodes in left subtree = #nodes in right subtree
  • this property applies over all nodes in the tree

[Diagram:Pic/three-bin-search-trees.png]