Skip to main content

Binary Search Trees

Binary Search Trees (BST) provide efficient search, insertion, and deletion operations with ordered data.

BST properties & validation​

  • BST Property: Left child < parent < right child for all nodes
  • Validation: Check if binary tree satisfies BST property
  • In-order Traversal: BST in-order traversal gives sorted sequence
  • Unique Structure: BST structure is not unique for given values
  • Search: Find node with given value (O(log n) average)
  • Insert: Add new node while maintaining BST property
  • Delete: Remove node while maintaining BST property
  • Successor/Predecessor: Find next/previous node in sorted order

BST to sorted array​

  • In-order Traversal: Convert BST to sorted array
  • Array to BST: Construct balanced BST from sorted array
  • Balanced BST: Ensure tree height is logarithmic
  • AVL Trees: Self-balancing BST with height balance property

Range queries​

  • Range Sum: Sum of values in given range
  • Range Count: Count nodes with values in range
  • Range Traversal: Visit all nodes in given range
  • Kth Smallest: Find kth smallest element in BST

BST construction from array​

  • Sorted Array: Construct balanced BST from sorted array
  • Pre-order Array: Construct BST from pre-order traversal
  • Post-order Array: Construct BST from post-order traversal
  • Level-order Array: Construct BST from level-order traversal