# 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:

# 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.
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.

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: