Scribd
Upload
8 views2 pages

BST Overview and Key Techniques

A Binary Search Tree (BST) is a binary tree where each node's left subtree contains smaller values and the right subtree contains larger values. Key operations include various tree traversals (inorder, preorder, postorder), and important properties such as sorted values through inorder traversal and average lookup time of O(log n). Optimization techniques involve using inorder for sorted access, tracking state with references, and considering time and space complexities for operations like search, insert, and delete.

Uploaded by

sumnadas346
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views2 pages

BST Overview and Key Techniques

A Binary Search Tree (BST) is a binary tree where each node's left subtree contains smaller values and the right subtree contains larger values. Key operations include various tree traversals (inorder, preorder, postorder), and important properties such as sorted values through inorder traversal and average lookup time of O(log n). Optimization techniques involve using inorder for sorted access, tracking state with references, and considering time and space complexities for operations like search, insert, and delete.

Uploaded by

sumnadas346
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Binary Search Tree (BST) Notes

1. What is a BST?

- A binary tree where for every node: Left < Root < Right

- All nodes in the left subtree are smaller, all in the right are greater.

2. Tree Traversals

- Inorder (L - Root - R): BST Inorder gives sorted array (ascending)

- Preorder (Root - L - R): Used to build BST (e.g. from preorder array)

- Postorder (L - R - Root): Used in deletion or depth calculation

3. Core Recursive Patterns

1. Traversal with Action (Inorder/Pre/Post)

2. Divide and Conquer (left = recurse(), right = recurse())

3. Carry state via parameters or reference (e.g. count, prev)

4. Important BST Properties

- Inorder traversal: Sorted values

- Min element: Leftmost node

- Max element: Rightmost node

- Height: Depends on balance

- Lookup time: O(log n) avg, O(n) worst

5. Common Approaches & Techniques

- Kth Smallest: Inorder + counter or BST Iterator

- BST Iterator: O(h) space stack-based traversal

- Validate BST: Range method or Inorder

- Recover BST: Find two violations in Inorder

- Two Sum in BST: 2 pointers using Inorder + Reverse Inorder

- LCA: Split point between p and q


Binary Search Tree (BST) Notes

- Build BST from Preorder: Use bounds + index

- Second Minimum Node: Inorder + track two values

6. Optimization Tips

- Use Inorder for sorted access

- Use range passing (min/max) to validate/build

- Use O(h) space with iterator

- Track state with global or reference vars

7. Time and Space Complexity

Search: O(log n) avg, O(n) worst

Insert/Delete: O(log n) avg, O(n) worst

Inorder Space: O(n)

Iterator Space: O(h)

8. Test Cases to Consider

- Left or Right skewed tree

- Single node tree

- Complete BST

- With/without duplicates

You might also like