1. Maximum Depth of Binary Tree

https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/555/

binary search and gather max depth:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int maxDepth(TreeNode* root) {
  15.         if(!root){
  16.             return 0;
  17.         }
  19.         return max(1+maxDepth(root->left), 1+maxDepth(root->right));
  20.     }
  21. };

2. Validate Binary Search Tree

https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/625/

recursion:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     bool isValidBST(TreeNode* root) {
  13.         return isValidBST(root, LONG_MIN, LONG_MAX);
  14.     }
  16.     bool isValidBST(TreeNode* root, long lower, long upper) {
  17.         if (!root) return true;
  19.         if(root->val <= lower || root->val >= upper)
  20.             return false;
  22.         return isValidBST(root->left, lower, root->val)
  23.             && isValidBST(root->right, root->val, upper);
  24.     }
  25. };

3. Symmetric Tree

https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/627/

recursion:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;

        return isSymmetric(root->left, root->right);
    }

private:
    bool isSymmetric(TreeNode* L, TreeNode* R){
        if(!L && !R)
            return true;
        else if(L && R){
            if(L->val != R->val)
                return false;
        } else if((!L && R) || (L && !R))
            return false;

        return isSymmetric(L->left, R->right) && isSymmetric(L->right, R->left);
    }
};

iteration:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;

        TreeNode* L;
        TreeNode* R;

        queue<TreeNode*> qL, qR;
        qL.push(root->left);
        qR.push(root->right);

        while (!qL.empty() && !qR.empty()){
            L = qL.front();
            qL.pop();
            R = qR.front();
            qR.pop();

            if (!L && !R)
                continue;
            if (!L || !R)
                return false;
            if (L->val != R->val)
                return false;

            qL.push(L->left);
            qL.push(L->right);
            qR.push(R->right);
            qR.push(R->left);
        }

        return true;
    }
};

4. Binary Tree Level Order Traversal

https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/628/

binary search recursion:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;

        levelOrder(root, 0, result);

        return result;
    }

private:
    void levelOrder(TreeNode* root, int layer, vector<vector<int>>& result) {
        if(!root)
            return;

        if((layer + 1) > result.size())
            result.push_back({});

        levelOrder(root->left, layer + 1, result);
        levelOrder(root->right, layer + 1, result);

        result[layer].push_back(root->val);
    }
};

5. Convert Sorted Array to Binary Search Tree

https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/631/

2 pointers and median:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root;

        root = sortedArrayToBST(nums, 0, nums.size());

        return root;
    }

private:
    TreeNode* sortedArrayToBST(vector<int> nums, int l, int r) {
        if(l >= r)
            return NULL;

        int m = (l + r) / 2;

        TreeNode* curr = new TreeNode(nums[m]);

        curr->left = sortedArrayToBST(nums, l, m);
        curr->right = sortedArrayToBST(nums, m+1, r);

        return curr;
    }
};