DSA Sheet - Day 21 BST

🌳 DSA Sheet – Day 21: Binary Search Trees (Part 2)

This section focuses on advanced BST operations like iterator design, tree recovery, and constructing BSTs efficiently using constraints.

📊 Progress Tracker

Progress: 0 / 5 Completed

Done	Problem	Practice	Level	Companies
	Recover Binary Search Tree	Solve	Medium	Amazon, Microsoft
	Populate Next Right Pointers	Solve	Medium	Amazon
	Construct BST from Preorder	Solve	Medium	Google
	BST Iterator	Solve	Medium	Amazon, LinkedIn
	Flatten BST to Sorted List	Solve	Medium	Amazon

🧠 Key Approaches

• Recover BST: Inorder traversal → detect swapped nodes
• Next Right Pointers: Level order OR constant space linking
• Construct BST: Use bounds (min, max)
• BST Iterator: Controlled inorder using stack
• Flatten BST: Inorder → rebuild right-skewed tree

⚡ Quick Cheatsheet

BST Iterator

stack st;

void pushAll(TreeNode* root){
  while(root){
    st.push(root);
    root = root->left;
  }
}
    

Recover BST

// inorder traversal
// find two nodes where order is violated
// swap their values
    

Construct BST from Preorder

TreeNode* build(int &i, int bound){
  if(i == n || preorder[i] > bound) 
    return NULL;

  TreeNode* root = new TreeNode(preorder[i++]);

  root->left = build(i, root->val);
  root->right = build(i, bound);

  return root;
}
    

🔥 Pro Tip

Advanced BST problems rely on:

• Inorder = sorted property
• Range constraints (min/max)
• Stack-based traversal control

Once you master these, BST becomes one of the easiest topics in interviews.

🏠 All Days ⬅ Previous Next ➡