🌳 BINARY TREE NOTES (Complete)
🔹 1. What is a Binary Tree?
A Binary Tree is a hierarchical data structure where each node has at most two children — a
left and a right child.
✅ Example:
1
/ \
2 3
/ \
4 5
🔹 2. Node Structure (Java)
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
[Link] = val;
left = right = null;
}
}
🔹 3. Types of Binary Trees
Type Description
Full Binary Tree Every node has 0 or 2 children
Complete Binary Tree All levels filled except possibly the last
Perfect Binary Tree All internal nodes have 2 children and all leaves are at same
level
Balanced Binary Tree Height difference between left and right ≤ 1
Degenerate Tree Every node has only one child (like a linked list)
🔹 4. Tree Traversals
Traversal means visiting every node exactly once.
A. Inorder (Left → Root → Right)
void inorder(TreeNode root) {
if (root == null) return;
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}
✅ Used in BST to get sorted order.
B. Preorder (Root → Left → Right)
void preorder(TreeNode root) {
if (root == null) return;
[Link]([Link] + " ");
preorder([Link]);
preorder([Link]);
}
✅ Used to create or clone trees.
C. Postorder (Left → Right → Root)
void postorder(TreeNode root) {
if (root == null) return;
postorder([Link]);
postorder([Link]);
[Link]([Link] + " ");
}
✅ Used to delete or free tree nodes.
D. Level Order (BFS)
void levelOrder(TreeNode root) {
if (root == null) return;
Queue<TreeNode> q = new LinkedList<>();
[Link](root);
while (![Link]()) {
TreeNode node = [Link]();
[Link]([Link] + " ");
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
}
✅ Used for BFS and printing level-wise data.
🔹 5. Important Tree Terms
Term Meaning
Root Topmost node
Leaf Node with no children
Height Longest path from root to a leaf
Depth Distance from root to current node
Subtre Any node and its descendants
e
🔹 6. Height of a Tree
int height(TreeNode root) {
if (root == null) return 0;
return 1 + [Link](height([Link]), height([Link]));
}
✅ Used in problems like Diameter or Balanced Tree.
🌿 Part 2 — Common Interview Tree
Problems
✅ 1. Check if Two Trees are Same
boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
if ([Link] != [Link]) return false;
return isSameTree([Link], [Link]) && isSameTree([Link], [Link]);
}
➡ Compares structure + values.
✅ 2. Mirror / Symmetric Tree
boolean isMirror(TreeNode a, TreeNode b) {
if (a == null && b == null) return true;
if (a == null || b == null) return false;
return ([Link] == [Link]) &&
isMirror([Link], [Link]) &&
isMirror([Link], [Link]);
}
➡ Used to check if tree is symmetric around its center.
✅ 3. Diameter of Binary Tree
int diameter = 0;
int diameterOfBinaryTree(TreeNode root) {
height(root);
return diameter;
}
int height(TreeNode root) {
if (root == null) return 0;
int left = height([Link]);
int right = height([Link]);
diameter = [Link](diameter, left + right);
return 1 + [Link](left, right);
}
➡ Longest path between any two nodes.
✅ 4. Lowest Common Ancestor (LCA)
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor([Link], p, q);
TreeNode right = lowestCommonAncestor([Link], p, q);
if (left == null) return right;
else if (right == null) return left;
else return root;
}
➡ Finds the lowest shared ancestor of two nodes.
✅ 5. Sum of All Nodes
int sum(TreeNode root) {
if (root == null) return 0;
return [Link] + sum([Link]) + sum([Link]);
}
➡ Used for tree sum or subtree sum problems.
✅ 6. Level Order Traversal (List<List<Integer>>)
List<List<Integer>> levelOrderList(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
[Link](root);
while (![Link]()) {
int size = [Link]();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = [Link]();
[Link]([Link]);
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
[Link](level);
}
return res;
}
➡ Returns nodes level-wise (useful for BFS-based problems).
✅ 7. Path Sum (Root to Leaf)
boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if ([Link] == null && [Link] == null)
return [Link] == targetSum;
return hasPathSum([Link], targetSum - [Link]) ||
hasPathSum([Link], targetSum - [Link]);
}
➡ Checks if a root-to-leaf path equals a given sum.
✅ 8. Check Balanced Tree
boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
int height(TreeNode node) {
if (node == null) return 0;
int left = height([Link]);
int right = height([Link]);
if (left == -1 || right == -1 || [Link](left - right) > 1)
return -1;
return 1 + [Link](left, right);
}
➡ Ensures height difference ≤ 1 for all nodes.
🔥 Summary to Remember
Concept Core Logic
Traversals Recursive DFS or BFS
Height / Depth 1 + max(left, right)
Diameter Use height + global variable
LCA Recursively find common ancestor
Balanced Tree Difference ≤ 1
Symmetric Tree Left and Right mirror check