📚 TREES — COMPLETE NOTES (Java + DSA Concepts)
📌 1️⃣ Tree Basics
● A tree is a hierarchical data structure with nodes connected by edges, starting from a root.
● Each node has zero or more child nodes.
● There is exactly one path from the root to any other node (no cycles).
● A tree with N nodes has exactly N–1 edges.
👉 Real-life examples:
✅ File system hierarchy
✅ Organization charts
✅ XML/JSON DOM
✅ Folder structures
📌 2️⃣ Tree Terminology
✅ Root → Topmost node
✅ Leaf → Node with no children
✅ Parent/Child → Relationship between levels
✅ Subtree → Tree formed by a node and its descendants
✅ Height → Longest path from root to leaf
✅ Depth → Distance from root
✅ Level → 0-based distance from root
✅ Balanced tree → Height difference of left/right ≤ 1
✅ Complete tree → All levels filled except possibly last
✅ Full tree → Each node has 0 or 2 children
✅ Perfect tree → All leaves at same depth and completely filled
📌 3️⃣ Tree Declaration (Java)
● class TreeNode {
● int val;
● TreeNode left;
● TreeNode right;
● TreeNode(int x) { val = x; }
● }
📌 4️⃣ Types of Trees
✅ Binary Tree (each node max 2 children)
✅ Binary Search Tree (BST)
✅ AVL Tree (self-balancing BST)
✅ Red-Black Tree
✅ Heap (complete tree)
✅ Trie (prefix tree)
✅ Segment / Fenwick Tree (range queries)
✅ N-ary Trees (general tree)
📌 5️⃣ Traversals (very important)
✅ Pre-order (root → left → right)
✅ In-order (left → root → right)
✅ Post-order (left → right → root)
✅ Level-order (BFS)
👉 Iterative or recursive
📌 6️⃣ Tree Properties
Property Description
N nodes N-1 edges
Height log N (balanced) or N (skewed)
Traversals O(N)
Insertion O(log N) (balanced), else O(N)
Search O(log N) (BST), else O(N)
📌 7️⃣ Applications of Trees
✅ Binary Search Trees → fast search
✅ Heaps → priority queues
✅ Expression parsing
✅ Tries → word prefix search
✅ Segment/Fenwick → range sum
✅ Balanced trees → indexing (e.g. databases)
📌 8️⃣ Mock Interview Theory Questions (with answers)
Q1. What is a tree?
A non-linear, hierarchical data structure with nodes connected without cycles.
Q2. Difference between tree and graph?
● Tree: hierarchical, no cycles
● Graph: more general, can have cycles
Q3. What is a BST?
Binary Search Tree → for any node, left < node < right.
Q4. What is a balanced tree?
Height difference of left/right subtrees ≤ 1 for every node.
Q5. What is a complete tree?
Every level fully filled except last, which is filled left to right.
Q6. What is a perfect tree?
All internal nodes have two children, and all leaves at the same level.
Q7. What is AVL tree?
Self-balancing BST with height balanced by rotations.
Q8. Difference between in-order and level-order?
● In-order → left-root-right (DFS)
● Level-order → level by level (BFS)
Q9. What is the height of a tree with one node?
0
Q10. When does a tree become skewed?
If all nodes only have left or only have right child, turning it into a linked list.
⚡ 9️⃣ Rapid-Fire One-Liners for Revision
✅ Tree = hierarchical
✅ No cycles
✅ N nodes → N-1 edges
✅ Height logN if balanced
✅ Traversals: pre, in, post, level
✅ Heap = complete binary tree
✅ Trie = prefix tree
✅ Segment tree = range queries
✅ AVL/RedBlack = self-balancing BST
✅ Used in file systems, XML, AI game states
🚀 🔟 Top 50 Tree Questions for Practice (LeetCode +
Company Tags)
No Question LC # Difficulty Companies
1 Maximum Depth of Binary Tree 104 Easy Amazon, TCS
2 Validate Binary Search Tree 98 Medium Microsoft,
Flipkart
3 Invert Binary Tree 226 Easy Google,
Amazon
4 Symmetric Tree 101 Easy Amazon
5 Balanced Binary Tree 110 Easy Amazon, Adobe
6 Same Tree 100 Easy Wipro, TCS
7 Binary Tree Paths 257 Easy Cognizant
8 Binary Tree Level Order Traversal 102 Medium Amazon
9 Binary Tree Zigzag Level Order Traversal 103 Medium Amazon,
Microsoft
10 Convert Sorted Array to BST 108 Easy Infosys
11 Path Sum 112 Easy Amazon
12 Lowest Common Ancestor of BST 235 Easy Facebook
13 Construct Binary Tree from Pre/Inorder 105 Medium Microsoft
14 Serialize and Deserialize Binary Tree 297 Hard Google,
Facebook
15 Diameter of Binary Tree 543 Easy Amazon
16 Sum Root to Leaf Numbers 129 Medium Amazon
17 Flatten Binary Tree to Linked List 114 Medium Google
18 Binary Tree Right Side View 199 Medium Facebook
19 Populating Next Right Pointers in Each Node 116 Medium Adobe
20 Binary Tree Maximum Path Sum 124 Hard Google
21 Count Good Nodes in Binary Tree 1448 Medium Amazon
22 All Nodes Distance K in Binary Tree 863 Medium Facebook
23 Sum of Left Leaves 404 Easy Wipro
24 Recover Binary Search Tree 99 Hard Google
25 Binary Search Tree Iterator 173 Medium Facebook,
Microsoft
26 Validate Binary Tree Nodes 1361 Medium Amazon
27 Vertical Order Traversal 987 Hard Google
28 Construct Binary Search Tree from Preorder 1008 Medium -
29 Check Completeness of a Binary Tree 958 Medium -
30 Delete Node in a BST 450 Medium -
31 Closest Binary Search Tree Value 270 Easy -
32 Binary Tree Cameras 968 Hard -
33 Kth Smallest Element in a BST 230 Medium Amazon,
Microsoft
34 Sum of Binary Tree Leaves 404 Easy -
35 Binary Tree Preorder Traversal 144 Easy -
36 Binary Tree Postorder Traversal 145 Easy -
37 Closest Leaf in a Binary Tree 742 Medium -
38 Serialize and Deserialize BST 449 Medium -
39 Lowest Common Ancestor of a Binary Tree 236 Medium Facebook
40 Construct Binary Tree from In/Postorder 106 Medium -
41 Increasing Order Search Tree 897 Easy -
42 Cousins in Binary Tree 993 Easy -
43 Find Duplicate Subtrees 652 Medium -
44 Distribute Coins in Binary Tree 979 Medium -
45 Binary Tree Tilt 563 Easy -
46 Smallest Subtree with all Deepest Nodes 865 Medium -
47 Binary Tree Coloring Game 1145 Medium -
48 Flip Equivalent Binary Trees 951 Medium -
49 Path Sum III 437 Medium -
50 Longest Univalue Path 687 Medium -
🧩 Ultimate Tree Tricks / Patterns Cheatsheet
Trick 1️⃣ — DFS Traversals (Pre, In, Post Order)
✅
Use Case:
✅
Any tree recursion
Search for conditions
Where? LC 94, 144, 145 (Amazon, Google)
Code Sketch
● // Inorder
● void inorder(TreeNode root) {
● if (root == null) return;
● inorder([Link]);
● // process
● inorder([Link]);
● }
Trick 2️⃣ — Iterative DFS with Stack
✅
Use Case:
✅
No recursion
Large depth trees
Where? LC 94 iterative (Amazon)
Pattern
● push root to stack
● pop, go left, push children
Trick 3️⃣ — BFS Level Order Traversal
✅
Use Case:
✅
Process level by level
Find depth
Where? LC 102 (Microsoft, Amazon)
Code Sketch
● Queue<TreeNode> q = new LinkedList<>();
● [Link](root);
● while (![Link]()) {
● int size = [Link]();
● for (int i = 0; i < size; i++) {
● TreeNode node = [Link]();
● // process
● if ([Link] != null) [Link]([Link]);
● if ([Link] != null) [Link]([Link]);
● }
● }
Trick 4️⃣ — Zigzag Level Order
✅
Use Case:
Alternating left/right
Where? LC 103
Pattern
● use deque
● flip level direction
Trick 5️⃣ — Diameter of Tree
✅
Use Case:
Longest path between two nodes
Where? LC 543 (Amazon)
Pattern
● height + left/right subtree
● update global diameter
Trick 6️⃣ — Maximum Depth of Tree
✅
Use Case:
Shortest / longest path
Where? LC 104
Pattern
● 1 + max(left, right) recursion
Trick 7️⃣ — Lowest Common Ancestor
✅
Use Case:
Two node path intersection
Where? LC 236, 235 (Facebook)
Pattern
● if left && right both found → return root
● else propagate up
Trick 8️⃣ — Check Symmetric Tree
✅
Use Case:
Mirror check
Where? LC 101
Pattern
● compare left subtree of left with right subtree of right
Trick 9️⃣ — Validate BST
✅
Use Case:
Rule check: left < root < right
Where? LC 98
Pattern
● pass min, max in recursion
Trick 🔟 — Flatten Binary Tree to Linked List
✅
Use Case:
In-place linked list style
Where? LC 114
Pattern
● use right pointers
● connect preorder path
Trick 1️⃣1️⃣ — Invert Binary Tree
✅
Use Case:
Mirror flip
Where? LC 226
Pattern
● swap left/right at every node
Trick 1️⃣2️⃣ — Serialize / Deserialize Tree
✅
Use Case:
Network data send
Where? LC 297
Pattern
● BFS or preorder with markers
● nulls as #
Trick 1️⃣3️⃣ — Balanced Tree Check
✅
Use Case:
Height balanced
Where? LC 110
Pattern
● get heights
● check diff ≤ 1
Trick 1️⃣4️⃣ — Path Sum Check
✅
Use Case:
Any to leaf target sum
Where? LC 112
Pattern
● subtract root value
● pass down recursion
Trick 1️⃣5️⃣ — Binary Tree Right Side View
✅
Use Case:
Only visible from right
Where? LC 199
Pattern
● BFS, track first node each level
Trick 1️⃣6️⃣ — Count Good Nodes
✅
Use Case:
Nodes with path max so far
Where? LC 1448
Pattern
● pass max so far down recursion
Trick 1️⃣7️⃣ — Find Duplicate Subtrees
✅
Use Case:
Find identical structures
Where? LC 652
Pattern
● serialize subtree
● track in map
Trick 1️⃣8️⃣ — Sum of Left Leaves
✅
Use Case:
Sum of only left children
Where? LC 404
Pattern
● check left child
● only leaf
Trick 1️⃣9️⃣ — Closest Value in BST
✅
Use Case:
Closest to target
Where? LC 270
Pattern
● binary search
● track closest
Trick 2️⃣0️⃣ — Recover BST
✅
Use Case:
2 swapped nodes in BST
Where? LC 99
Pattern
● inorder traversal
● find 2 anomalies
Trick 2️⃣1️⃣ — Binary Tree Cameras
✅
Use Case:
Cover all nodes
Where? LC 968
Pattern
● place camera on parent
● greedy recursion
Trick 2️⃣2️⃣ — Longest Univalue Path
✅
Use Case:
Same value path
Where? LC 687
Pattern
● DFS on values
● track length
Trick 2️⃣3️⃣ — Smallest Subtree with All Deepest Nodes
✅
Use Case:
Deepest subtree
Where? LC 865
Pattern
● find depth
● lowest common ancestor of deepest
Trick 2️⃣4️⃣ — Increasing Order Search Tree
✅
Use Case:
Flatten to increasing list
Where? LC 897
Pattern
● inorder
● connect right
Trick 2️⃣5️⃣ — Check Tree Completeness
✅
Use Case:
Is it complete binary tree
Where? LC 958
Pattern
● BFS
● once null child seen → no more children allowed
Trick 2️⃣6️⃣ — Count Paths Sum to K
✅
Use Case:
Any path sums
Where? LC 437
Pattern
● prefix sums
● hashmap
Trick 2️⃣7️⃣ — Serialize BST
✅
Use Case:
Save BST
Where? LC 449
Pattern
● preorder
● avoid nulls
Trick 2️⃣8️⃣ — Maximum Path Sum
✅
Use Case:
Path with any nodes
Where? LC 124
Pattern
● choose left/right/gap
● global max
Trick 2️⃣9️⃣ — Closest Leaf in Binary Tree
✅
Use Case:
Shortest distance leaf
Where? LC 742
Pattern
● BFS after mapping parents
Trick 3️⃣0️⃣ — Distribute Coins in Binary Tree
✅
Use Case:
Balance coins
Where? LC 979
Pattern
● postorder
● transfer coins