insert, delete, search - O(logn)
The key of the current node must be greater than the key of the left child node and less than the key of the right child node.
Non-linear datastructure
- e.g of linear data structures arrays, queues, linkedlists, stacks
root, child, parent, ansestor, desendant, leaf, siblings
Binary tree - node with at most 2 children
BFS - breadth first search
DFS - depth first search preorder, postorder, inorder
Inorder - best for bst, would always return a sorted list
- traverse left
- display node
- traverse right
Preorder
- display node
- traverse left
- traverse right
Postorder
- traverse left
- traverse right
- display node
As with all binary trees, one may conduct a pre-order traversal or a post-order traversal, but neither are likely to be useful for binary search trees. An in-order traversal of a binary search tree will always result in a sorted list of node items (numbers, strings or other comparable items).
O(n) as every node must be visited