285. (Locked)Inorder Successor in BST

Difficulty: Medium

Frequency: N/A

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (!root || !p) return NULL;
        TreeNode *suc;
        while (root) {
            if (root->val <= p->val) root = root->right;
            else {
                suc = root;
                root = root->left;
            }
        }
        return suc;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

333. (Locked)Largest BST Subtree

Difficulty: Medium

Frequency: N/A

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.
Note:
A subtree must include all of its descendants.
Here’s an example:
    10
    / \
   5  15
  / \   \ 
 1   8   7

The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree’s size, which is 3.

Hint:
  1. You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.
Follow up:
Can you figure out ways to solve it with O(n) time complexity?

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        if (isValid(root, NULL, NULL)) return count(root);
        return max(largestBSTSubtree(root->left), largestBSTSubtree(root->right));
    }
    bool isValid(TreeNode* node, TreeNode* min, TreeNode* max) {
        if (!node) return true;
        if (min && node->val <= min->val || max && node->val >= max->val) return false;
        return isValid(node->left, min, node) && isValid(node->right, node, max);
    }
    int count(TreeNode* node) {
        if (!node) return 0;
        if (!node->left && !node->right) return 1;
        return 1 + count(node->left) + count(node->right);
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

236. Lowest Common Ancestor of a Binary Tree

Difficulty: Medium

Frequency: N/A

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode * right = lowestCommonAncestor(root->right, p, q);
        return !left ? right : !right ? left : root;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

094. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?


Questions:
1. Recursive or iteratively

Test Cases:

1. [#] empty
2. [1] root only
3. [1, 2, #, 3, #, 4] all left
4. [1, #, 2, #, #, #, 3] all right
5. [1, #, 2, 3] normal

Solution 1:
Data structure:
vector, tree
Method:
Recursive:
1. helper(node->left)
2. push(node->val)
3. helper(node->right)
Complexity:
Runtime:
worst case: o(n^2)
average: o(nlogn)
Space:
o(n)
Code:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorderTraverse(root, result);
        return result;
    }
    void inorderTraverse(TreeNode *node, vector<int>& result) {
        if (!node) return;
        inorderTraverse(node->left, result);
        result.push_back(node->val);
        inorderTraverse(node->right, result);
    }
};

 Solution 2:
Data structure:
Method:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. Tree Traversals:

173. Binary Search Tree Iterator

Difficulty: Medium

Frequency: N/A

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
private:
    stack<TreeNode*> myStack;
    void pushLeft(TreeNode *node) {
        for (; node != NULL; node = node->left) myStack.push(node);
    }
public:
    BSTIterator(TreeNode *root) {
        pushLeft(root);
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !myStack.empty();
    }

    /** @return the next smallest number */
    int next() {
        TreeNode *tmp = myStack.top();
        myStack.pop();
        pushLeft(tmp->right);
        return tmp->val;
    }
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

230. Kth Smallest Element in a BST

Difficulty: Medium

Frequency: N/A

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Hint:

  1. Try to utilize the property of a BST.
  2. What if you could modify the BST node’s structure?
  3. The optimal runtime complexity is O(height of BST).

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int val = INT_MAX;
        findK(root, k, val);
        return val;
    }
    void findK(TreeNode* node, int& k, int& val) {
        if (!node) return;
        findK(node->left, k, val);
        k--;
        if (k == 0) {
            val = node->val;
            return;
        }
        findK(node->right, k, val);
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

144. Binary Tree Preorder Traversal

Difficulty: Medium

Frequency: N/A

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traverse(root, result);
        return result;
    }
    void traverse(TreeNode* node, vector<int>& result) {
        if (!node) return;
        result.push_back(node->val);
        traverse(node->left, result);
        traverse(node->right, result);
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: