Back to curriculum

Binary Search Trees Cheat Sheet

  • Quick summary: a kind of binary tree where nodes to the left are smaller, and nodes to the right are larger than the current node.
  • Important facts:
    • Nodes of a binary search tree (BST) are ordered in a specific way:
      • All nodes to the left of the current node are smaller (or sometimes smaller or equal) than the current node.
      • All nodes to the right of the current node are larger than the current node.
    • Duplicate nodes are usually not allowed.
  • Pros:
    • Balanced BSTs are moderately performant for all operations.
    • Since BST is sorted, reading its nodes in sorted order can be done in O(n), and search for a node closest to a value can be done in O(log(n))
  • Cons:
    • Same as trees in general: no constant time operations, performance degradation in unbalanced trees.
  • Time complexity (worst case):
    • Access: O(n)
    • Search: O(n)
    • Insertion: O(n)
    • Deletion: O(n)
  • Time complexity (average case):
    • Access: O(log(n))
    • Search: O(log(n))
    • Insertion: O(log(n))
    • Deletion: O(log(n))
  • See also:

Show Cheatsheet

Binary Search Trees Definition: A type of binary trees that takes ordering into account.

Learn

Interview Problems

Why do I see duplicate challenges? You'll see duplicates because a question may fall into different categories. We keep them here because we believe that it is good to sporadically review old problems. They are optional if already completed-- but reviewing them (and more importantly re-doing them with the new knowledge) will ensure that you've internalized the patterns.

Related Lessons