Binary Search Tree

O(log n) avg

Colour Guide

Scanning / Comparing

Found / Success

Newly Inserted

Not Found / Deleting

Pseudocode

search(node, val): if node is null or node.val == val: return node if val < node.val: return search(node.left, val) return search(node.right, val)

BST Info

Nodes0

Height–

Root–

Step Log

Complexity

Search (avg)	O(log n)
Insert (avg)	O(log n)
Delete (avg)	O(log n)
Worst case	O(n)