Tree-Based Easy Problem

Tree data structures are foundational in computer science and frequently appear in technical interviews. Today, I tackled several binary tree questions on LeetCode from traversals to symmetry, balance checks, and more.

♻️ 1. Preorder Traversal of Binary Tree

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
    void preorder(TreeNode* node, vector<int>& res) {
        if (!node) return;
        res.push_back(node->val);
        preorder(node->left, res);
        preorder(node->right, res);
    }
};

Key Takeaway: Always prefer passing result by reference to avoid global state issues.

🔄 2. Invert Binary Tree (Flip Left and Right)

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

Key Takeaway: Tree inversion is best solved with post-order traversal.

🤠 3. Symmetric Tree

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isMirror(root->left, root->right);
    }
    bool isMirror(TreeNode* t1, TreeNode* t2) {
        if (!t1 && !t2) return true;
        if (!t1 || !t2 || t1->val != t2->val) return false;
        return isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
    }
};

Key Takeaway: Comparing left with right recursively works efficiently.

📈 4. Check if Tree is Balanced

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return checkDepth(root) != -1;
    }
    int checkDepth(TreeNode* root) {
        if (!root) return 0;
        int left = checkDepth(root->left);
        int right = checkDepth(root->right);
        if (left == -1 || right == -1 || abs(left - right) > 1) return -1;
        return max(left, right) + 1;
    }
};

Key Takeaway: Combine depth calculation and imbalance check in a single pass.

🌿 5. Has Path Sum

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        if (!root->left && !root->right) return targetSum == root->val;
        return hasPathSum(root->left, targetSum - root->val) ||
               hasPathSum(root->right, targetSum - root->val);
    }
};

Key Takeaway: Subtract values along the path and check at leaves.

📊 6. Pascal’s Triangle (Bonus)

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        res.push_back({1});
        for (int i = 1; i < numRows; ++i) {
            vector<int> row = {1};
            for (int j = 0; j < res.back().size() - 1; ++j) {
                row.push_back(res.back()[j] + res.back()[j + 1]);
            }
            row.push_back(1);
            res.push_back(row);
        }
        return res;
    }
};

Key Takeaway: Use the previous row to compute the next. A classic DP + pattern problem.

Lessons Learned

• Recursive traversal is powerful, but you must manage state carefully.

• Optimize by merging logic (e.g., depth & balance in one function).

• Don’t overcomplicate; sometimes mirror checks are more efficient than inversion.

What's Next?

• Binary Tree Level Order Traversal

• Diameter of Binary Tree

• Lowest Common Ancestor

• Serialize and Deserialize Tree

• Construct Tree from Traversals