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);
result.add(p.val); // Add before going to children
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<>();
LinkedList<Integer> ans = new LinkedList<>();
if (root == null) {
return ans;
}
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
ans.add(node.val);
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();
result.add(node.val); // Add after all left children
p = node.right;
}
}
return result;
}*Another Iterative In-Order Traversal
public List<Integer> inorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
LinkedList<Integer> ans = new LinkedList<>();
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();
ans.add(p.val);
p = p.right;
}
return ans;
}Post-Order Traversal
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
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<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
output.addFirst(node.val);
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) {
result.add(root.val);
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);
}
result.add(root.val);
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);
result.add(root.val);
}
}
}Level Order Traversal
BFS
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
if(root == null) return wrapList;
queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
List<Integer> subList = new LinkedList<Integer>();
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);
subList.add(queue.poll().val);
}
wrapList.add(subList);
}
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()) {
result.add(new ArrayList<Integer>());
}
result.get(depth).add(root.val);
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