# Trees

## Types of Binary Trees

https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

A full binary tree is a tree in which every node has either 0 or 2 children.

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.

A perfect binary tree is a tree with all leaves are at the same level, and every parent has two children.

## Binary Tree Node

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/``````

## Binary Tree Traversal

### Iterative, Non-recursive Implementation with Stack

#### Pre-Order Traversal

``````public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode node = stack.pop();
p = node.right;
}
}
return result;
}``````

*Another Iterative Pre-Order Traversal

``````public List<Integer> preorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
if (root == null) {
return ans;
}
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return ans;
}``````

#### In-Order Traversal

``````public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode node = stack.pop();
p = node.right;
}
}
return result;
}``````

*Another Iterative In-Order Traversal

``````public List<Integer> inorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
if (root == null) {
return ans;
}
TreeNode p = root;
while (p != null || !stack.isEmpty()) {
while (p != null) {
stack.push(p);
p = p.left;
}
p = stack.pop();
p = p.right;
}
return ans;
}``````

#### Post-Order Traversal

``````public List<Integer> postorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.addFirst(p.val);  // Reverse the process of preorder
p = p.right;             // Reverse the process of preorder
} else {
TreeNode node = stack.pop();
p = node.left;           // Reverse the process of preorder
}
}
return result;
}``````

*Another Iterative Post-Order Traversal

``````public List<Integer> postorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
if (root == null) {
return output;
}

stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
return output;
}``````

### Recursive Implementation

#### Pre-Order Traversal

``````class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
recursivePreorderTraversal(root, result);
return result;
}
void recursivePreorderTraversal(TreeNode root, List<Integer> result) {
if (root != null) {
recursivePreorderTraversal(root.left, result);
recursivePreorderTraversal(root.right, result);
}
}
}``````

#### In-Order Traversal

``````class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
recursiveInorderTravesal(root, result);
return result;
}
void recursiveInorderTravesal(TreeNode root, List<Integer> result) {
if (root != null) {
if (root.left != null) {
recursiveInorderTravesal(root.left, result);
}
if (root.right != null) {
recursiveInorderTravesal(root.right, result);
}
}
}
}``````

#### Post-Order Traversal

``````class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
recursivePreorderTraversal(root, result);
return result;
}
void recursivePreorderTraversal(TreeNode root, List<Integer> result) {
if (root != null) {
recursivePreorderTraversal(root.left, result);
recursivePreorderTraversal(root.right, result);
}
}
}``````

### Level Order Traversal

#### BFS

``````public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {

if(root == null) return wrapList;

queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
for(int i=0; i<levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);
}
}
return wrapList;
}
}``````

#### DFS

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
levelOrderHelper(root, 0, result);
return result;
}
void levelOrderHelper(TreeNode root, int depth, List<List<Integer>> result) {
if (root == null) {
return;
}
if (depth == result.size()) {
}
levelOrderHelper(root.left, depth + 1, result);
levelOrderHelper(root.right, depth + 1, result);

}
}``````

## Maximum Depth of Binary Tree

Recursive

``````class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return 1 + Math.max(left, right);
}
}``````

## Symmetric Tree

https://leetcode.com/articles/symmetric-tree/

Recursive

``````public boolean isSymmetric(TreeNode root) {
return root == null || isMirror(root.left, root.right);
}
boolean isMirror(TreeNode node1, TreeNode node2) {
if (node1 == null && node2 == null) return true;
if (node1 == null || node2 == null) return false;
if (node1.val != node2.val) return false;
return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}``````

Iterative

``````public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
Queue < TreeNode > q = new LinkedList < TreeNode > ();
q.offer(root.left);
q.offer(root.right);
while (!q.isEmpty()) {
TreeNode n1 = q.poll();
TreeNode n2 = q.poll();
if (n1 == null && n2 == null) continue;
if (n1 == null && n2 != null) return false;
if (n1 != null && n2 == null) return false;
if (n1.val != n2.val) return false;
q.offer(n1.left);
q.offer(n2.right);
q.offer(n1.right);
q.offer(n2.left);
}
return true;
}``````

## Binary Search Tree (BST)

``````    public boolean isValidBST(TreeNode root) {
if (root == null) return true;
return isValidSubtree(root, null, null);
}
boolean isValidSubtree (TreeNode root, Integer min, Integer max) {
if (root == null) return true;
if ((min != null && root.val <= min) ||  (max != null && root.val >= max)) return false;
return isValidSubtree (root.left, min, root.val) && isValidSubtree(root.right, root.val, max);
}``````

Last updated