# Leetcode: Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree `{3,9,20,#,#,15,7}`,

```    3
/ \
9  20
/  \
15   7```

return its level order traversal as:

```[
[3],
[9,20],
[15,7]
]```

1. One Queue Solution — Better

```public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
//one queue
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (root != null) {
q.offer(root);
}
while (!q.isEmpty()) {
ArrayList<Integer> levelNodes = new ArrayList<>();
int size = q.size(); //this is the # of nodes in current level
for (int i = 0; i < size; i++) {
TreeNode curr = q.poll();
if (curr.left != null) {
q.offer(curr.left);
}
if (curr.right != null) {
q.offer(curr.right);
}
}
}
return result;
}```

2. Two Queues Solution — Easier to Understand

```public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<ArrayList<Integer>> output= new ArrayList<ArrayList<Integer>>();
if(root==null){
return output;
}
ArrayList<TreeNode> current = new ArrayList<TreeNode>();
ArrayList<TreeNode> children = new ArrayList<TreeNode>();
while(current.size()!=0){
children = new ArrayList<TreeNode>();
ArrayList<Integer> levelNodes= new ArrayList<Integer>();
for(TreeNode t : current){
if(t.left!=null){
}
if(t.right!=null){
}
}
current = children;
}
return output;
}```

Share

# Leetcode: Validate Binary Search Tree

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.
```public boolean isValidBST(TreeNode root) {
return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

}
//return if the root val is within the [min,max] range
public boolean isValidBSTHelper(TreeNode root, int min, int max) {
if (root == null) {
return true;
}
if (min > root.val || root.val > max) {
return false;
}
return isValidBSTHelper(root.left, min, root.val - 1) &&
isValidBSTHelper(root.right, root.val + 1, max);
}```

# Leetcode: Flatten Binary Tree to Linked List

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```

Hints:

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

```public class Solution {
public void flatten(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root==null){
return;
}
if(root.left==null){
flatten(root.right);
return;
}

TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
if(right!=null){
//find the right most element in root's left subtree
//add root's right subtree to the element as a right child
TreeNode runner = left;
while(runner.right!=null){
runner = runner.right;
}
runner.right = right;
}
root.right=left;
flatten(left);

}```

# Leetcode: Construct Binary Tree from Inorder and Postorder Traversal

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

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

```/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
// Start typing your Java solution below
// DO NOT write main() function
if(inorder.length==0){
return null;
}

//last element of postorder is the root
TreeNode root = new TreeNode(postorder[postorder.length-1]);
//find the root element in the inorder array
//elements occur before it are in its left sub-tree
//elements occur after it are in its right sub-tree
int index = 0;
for(int i=0;i<inorder.length;i++){
if(inorder[i]==root.val){
index = i;
break;
}
}
int[] leftInOrder = new int[index];
int[] leftPostOrder = new int[index];
int[] rightInOrder = new int[inorder.length-index-1];
int[] rightPostOrder = new int[inorder.length-index-1];

for(int i=0;i<inorder.length;i++){
if(i<index){
leftInOrder[i] = inorder[i];
}
if(i>index){
rightInOrder[i-index-1] = inorder[i];
}
}

for(int i=0;i<postorder.length-1;i++){
if(i<index){
leftPostOrder[i] = postorder[i];
}else{
rightPostOrder[i-index]=postorder[i];
}
}

root.left = buildTree(leftInOrder,leftPostOrder);
root.right = buildTree(rightInOrder,rightPostOrder);
return root;
}
}```

# Leetcode: 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]`.

1. Recursive Version

```public ArrayList<Integer> inorderTraversal(TreeNode root) {
//recursive version
ArrayList<Integer> result = new ArrayList<>();
traversalHelper(root, result);
return result;
}

public void traversalHelper(TreeNode root, ArrayList<Integer> result) {
if (root == null) {
return;
}
traversalHelper(root.left, result);
traversalHelper(root.right, result);
}```

2. Non-recursive Version

```public ArrayList<Integer> inorderTraversal(TreeNode root) {
//non-recursive version
ArrayList<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.empty()) {
TreeNode left = curr;
while (left != null) {
stack.push(left);
left = left.left;
}
curr = stack.pop();