# 117. Populating Next Right Pointers in Each Node II

Difficulty: Hard

Frequency: N/A

Follow up for problem “Populating Next Right Pointers in Each Node“.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

```         1
/  \
2    3
/ \    \
4   5    7
```

After calling your function, the tree should look like:

```         1 -> NULL
/  \
2 -> 3 -> NULL
/ \    \
4-> 5 -> 7 -> NULL```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for binary tree with next pointer.
*  int val;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
if (!root) return;
root->next = NULL;
while (cur) {
while (nn) {
if (ln) {
if (rn) ln->next = rn;
else {
while (tmp) {
if (!tmp->next) {
ln->next = NULL;
break;
} else if (tmp->next->left) {
ln->next = tmp->next->left;
break;
} else if (tmp->next->right) {
ln->next = tmp->next->right;
break;
}
tmp = tmp->next;
}
}
}
if (rn) {
while (tmp) {
if (!tmp->next) {
rn->next = NULL;
break;
} else if (tmp->next->left) {
rn->next = tmp->next->left;
break;
} else if (tmp->next->right) {
rn->next = tmp->next->right;
break;
}
tmp = tmp->next;
}
}
nn = nn->next;
}
while (cur) {
if (cur->left) {
cur = cur->left;
break;
} else if (cur->right) {
cur = cur->right;
break;
}
cur = cur->next;
}
}
}
};
```

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

Things to learn:

# 098. Validate Binary Search Tree

Difficulty: Medium

Frequency: N/A

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

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:
bool isValidBST(TreeNode* root) {
return checkBST(root, NULL, NULL);
}
bool checkBST(TreeNode* node, TreeNode* min, TreeNode* max) {
if (!node) return true;
if (min && node->val <= min->val || max && node->val >= max->val) return false;
return checkBST(node->left, min, node) && checkBST(node->right, node, max);
}
};
```

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

Things to learn:

# 116. Populating Next Right Pointers in Each Node

Difficulty: Medium

Frequency: N/A

Given a binary tree

```    struct TreeLinkNode {
}
```

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to `NULL`.

Initially, all next pointers are set to `NULL`.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

```         1
/  \
2    3
/ \  / \
4  5  6  7
```

After calling your function, the tree should look like:

```         1 -> NULL
/  \
2 -> 3 -> NULL
/ \  / \
4->5->6->7 -> NULL```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for binary tree with next pointer.
*  int val;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
if (!root) return;
root->next = NULL;
while (cur) {
while (nn) {
if (ln) ln->next = rn;
if (rn) {
if (nn->next) rn->next = nn->next->left;
else rn->next = NULL;
}
nn = nn->next;
}
cur = cur->left;
}
}
};
```

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

Things to learn:

# 106. Construct Binary Tree from Inorder and Postorder Traversal

Difficulty: Medium

Frequency: N/A

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

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* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty() || postorder.empty() || inorder.size() != postorder.size()) return NULL;
return generateTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
TreeNode* generateTree(vector<int>& inorder, int is, int ie, vector<int>& postorder, int ps, int pe) {
if (ps > pe) return NULL;
TreeNode *node = new TreeNode(postorder[pe]);
int mid = is;
while (mid <= ie) {
if (inorder[mid] == postorder[pe]) break;
mid++;
}
node->left = generateTree(inorder, is, mid - 1, postorder, ps, ps + mid - is - 1);
node->right = generateTree(inorder, mid + 1, ie, postorder, pe + mid - ie, pe - 1);
return node;
}
};
```

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

Things to learn:

# 105. Construct Binary Tree from Preorder and Inorder Traversal

Difficulty: Medium

Frequency: N/A

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

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* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty() || inorder.empty() || preorder.size() != inorder.size()) return NULL;
return generateTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
TreeNode* generateTree(vector<int>& preorder, int ps, int pe, vector<int>& inorder, int is, int ie) {
if (ps > pe) return NULL;
TreeNode *node = new TreeNode(preorder[ps]);
int mid = is;
while (mid <= ie) {
if (inorder[mid] == preorder[ps]) break;
mid++;
}
node->left = generateTree(preorder, ps + 1, ps + mid - is, inorder, is, mid - 1);
node->right = generateTree(preorder, pe - ie + mid + 1, pe, inorder, mid + 1, ie);
return node;
}
};
```

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

Things to learn:

# 109. Convert Sorted List to Binary Search Tree

Difficulty: Medium

Frequency: N/A

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* 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:
while(fast && fast->next) {
fast = fast->next->next;
pre = slow;
slow = slow->next;
}
if (pre) pre->next = NULL;
TreeNode *root = new TreeNode(slow->val);
root->right = sortedListToBST(slow->next);
return root;
}
};
```

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

Things to learn:

# 114. Flatten Binary Tree to Linked List

Difficulty: Medium

Frequency: N/A

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

```         1
/ \
2   5
/ \   \
3   4   6
```

The flattened tree should look like:

```   1
\
2
\
3
\
4
\
5
\
6
```

click to show hints.

Hints:If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

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:
void flatten(TreeNode* root) {
TreeNode *cur = root;
while(cur) {
if (cur->left) {
TreeNode *tmp = cur->left;
while(tmp->right) {
tmp = tmp->right;
}
tmp->right = cur->right;
cur->right = cur->left;
cur->left = NULL;
}
cur = cur->right;
}
}
};
```

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

Things to learn: