DSA Sheet - Day 17 Binary Trees

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

This section focuses on structural tree problems like diameter, balance checking, subtree detection, and advanced traversal techniques.

📊 Progress Tracker

Progress: 0 / 6 Completed

Done	Problem	Practice	Level	Companies
	Morris Inorder Traversal	Solve	Easy	Google, Apple
	Diameter of Binary Tree	Solve	Easy	Meta, Adobe
	Same Tree (Identical Trees)	Solve	Easy	Amazon, Apple
	Symmetric Tree (Mirror)	Solve	Easy	Amazon, Google
	Subtree of Another Tree	Solve	Easy	Google, Microsoft
	Balanced Binary Tree	Solve	Easy	Amazon

🧠 Key Approaches

• Morris Traversal: Threaded tree (no recursion / stack)
• Diameter: Height + max path tracking
• Identical Trees: Recursive comparison
• Mirror Tree: Left vs right comparison
• Subtree: Check same tree at each node
• Balanced Tree: Height check with early exit

⚡ Quick Cheatsheet

Diameter of Binary Tree

int diameter = 0;

int height(TreeNode* root){
  if(!root) return 0;

  int l = height(root->left);
  int r = height(root->right);

  diameter = max(diameter, l + r);

  return 1 + max(l, r);
}
    

Same Tree

bool isSame(TreeNode* p, TreeNode* q){
  if(!p && !q) return true;
  if(!p || !q) return false;

  return p->val == q->val &&
         isSame(p->left, q->left) &&
         isSame(p->right, q->right);
}
    

Balanced Binary Tree

int check(TreeNode* root){
  if(!root) return 0;

  int l = check(root->left);
  if(l == -1) return -1;

  int r = check(root->right);
  if(r == -1) return -1;

  if(abs(l - r) > 1) return -1;

  return 1 + max(l, r);
}
    

🔥 Pro Tip

Most tree problems reduce to:

• Height calculation
• DFS recursion patterns
• Comparing subtrees

If you understand how to combine these, you can solve 70% of tree interview questions.

🏠 All Days ⬅ Previous Next ➡