Chapter 16
Trees in Java
Java Data Structures & Algorithms
A Tree is a hierarchical, non-linear data structure made of nodes connected by edges, with no cycles.
Unlike arrays or linked lists, trees branch out — making them perfect for representing hierarchical
relationships like file systems, organization charts, or DOM structures.
1 Core Terminology
Before writing any code, understand these terms clearly:
1 ← Root (no parent)
/ \
2 3 ← Internal nodes
/ \ \
4 5 6 ← Leaf nodes (no children)
Term Meaning
Root Topmost node, has no parent
Leaf Node with no children
Height Longest path from node to a leaf
Depth Distance from root to a node
Degree Number of children a node has
Subtree A node and all its descendants
Edge Connection between two nodes
Level Depth + 1 (root is level 1)
2 Types of Trees
Type Rule
Binary Tree Each node has at most 2 children
Full Binary Tree Every node has 0 or 2 children
Complete Binary Tree All levels filled except possibly last (filled left to right)
Perfect Binary Tree All internal nodes have 2 children, all leaves at same level
Balanced Binary Tree Height difference between left & right subtree ≤ 1
Degenerate Tree Every node has only 1 child (like a linked list)
3 Binary Tree Node Structure in Java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
// Constructor
TreeNode(int val) {
[Link] = val;
[Link] = null;
[Link] = null;
}
}
Building a Tree Manually
public class Chapter16Trees {
public static void main(String[] args) {
// Build this tree:
// 1
// / \
// 2 3
// / \ \
// 4 5 6
TreeNode root = new TreeNode(1);
[Link] = new TreeNode(2);
[Link] = new TreeNode(3);
[Link] = new TreeNode(4);
[Link] = new TreeNode(5);
[Link] = new TreeNode(6);
}
}
4 Height of a Tree
Height = longest path from current node down to any leaf.
Height of leaf node = 0
Height of null = -1
Height of node = 1 + max(height(left), height(right))
public static int height(TreeNode root) {
if (root == null) return -1; // base case
int leftHeight = height([Link]);
int rightHeight = height([Link]);
return 1 + [Link](leftHeight, rightHeight);
}
// For the tree above:
// height(4) = 0, height(5) = 0, height(6) = 0
// height(2) = 1 + max(0, 0) = 1
// height(3) = 1 + max(-1, 0) = 1
// height(1) = 1 + max(1, 1) = 2 ✓
5 Count Nodes
public static int countNodes(TreeNode root) {
if (root == null) return 0;
return 1 + countNodes([Link]) + countNodes([Link]);
}
Time Complexity: O(n) | Space Complexity: O(h) — h = height of tree (recursion stack)
6 Count Leaf Nodes
public static int countLeaves(TreeNode root) {
if (root == null) return 0;
if ([Link] == null && [Link] == null) return 1; // it's a leaf
return countLeaves([Link]) + countLeaves([Link]);
}
Time Complexity: O(n) | Space Complexity: O(h)
7 Diameter of a Tree
Diameter = longest path between any two nodes (path may or may not pass through root).
1
/ \
2 3
/ \
4 5
Diameter = 3 (path: 4 → 2 → 5 OR 4 → 2 → 1 → 3)
static int diameter = 0; // global tracker
public static int findDiameter(TreeNode root) {
heightForDiameter(root);
return diameter;
}
private static int heightForDiameter(TreeNode root) {
if (root == null) return -1;
int leftH = heightForDiameter([Link]);
int rightH = heightForDiameter([Link]);
// diameter through current node = leftH + rightH + 2
diameter = [Link](diameter, leftH + rightH + 2);
return 1 + [Link](leftH, rightH);
}
Time Complexity: O(n) | Space Complexity: O(h)
8 Check if Tree is Symmetric (Mirror)
public static boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isMirror([Link], [Link]);
}
private static boolean isMirror(TreeNode l, TreeNode r) {
if (l == null && r == null) return true; // both null ✓
if (l == null || r == null) return false; // one null ✗
return ([Link] == [Link])
&& isMirror([Link], [Link])
&& isMirror([Link], [Link]);
}
Time Complexity: O(n) | Space Complexity: O(h)
9 Check if Balanced (Height-Balanced)
A tree is balanced if for every node, |height(left) - height(right)| ≤ 1.
public static boolean isBalanced(TreeNode root) {
return checkHeight(root) != -2; // -2 is our "unbalanced" signal
}
private static int checkHeight(TreeNode root) {
if (root == null) return -1;
int leftH = checkHeight([Link]);
if (leftH == -2) return -2; // propagate unbalanced signal up
int rightH = checkHeight([Link]);
if (rightH == -2) return -2;
if ([Link](leftH - rightH) > 1) return -2; // unbalanced here
return 1 + [Link](leftH, rightH);
}
Time Complexity: O(n) | Space Complexity: O(h)
10 Path Sum — Does a Root-to-Leaf Path Equal Target?
public static boolean hasPathSum(TreeNode root, int target) {
if (root == null) return false;
target -= [Link]; // subtract current node's value
if ([Link] == null && [Link] == null) return target == 0; // leaf
check
return hasPathSum([Link], target) || hasPathSum([Link], target);
}
Time Complexity: O(n) | Space Complexity: O(h)
11 Right Side View of Tree
What nodes do you see if you look at the tree from the right side? (Last node of each level)
import [Link].*;
public static List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
[Link](root);
while (![Link]()) {
int size = [Link]();
for (int i = 0; i < size; i++) {
TreeNode node = [Link]();
if (i == size - 1) [Link]([Link]); // last node of level
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
}
return result;
}
Time Complexity: O(n) | Space Complexity: O(n)
12 Full Runnable Java Program
import [Link].*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { [Link] = val; }
}
public class Chapter16Trees {
static int diameter = 0;
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
[Link] = new TreeNode(2);
[Link] = new TreeNode(3);
[Link] = new TreeNode(4);
[Link] = new TreeNode(5);
[Link] = new TreeNode(6);
[Link]("Height: " + height(root)); // 2
[Link]("Count Nodes: " + countNodes(root)); // 6
[Link]("Count Leaves: " + countLeaves(root));// 3
[Link]("Diameter: " + findDiameter(root)); // 4
[Link]("Balanced: " + isBalanced(root)); // true
[Link]("Symmetric: " + isSymmetric(root)); // false
[Link]("Right View: " + rightSideView(root));// [1, 3, 6]
}
static int height(TreeNode r) {
if (r == null) return -1;
return 1 + [Link](height([Link]), height([Link]));
}
static int countNodes(TreeNode r) {
if (r == null) return 0;
return 1 + countNodes([Link]) + countNodes([Link]);
}
static int countLeaves(TreeNode r) {
if (r == null) return 0;
if ([Link] == null && [Link] == null) return 1;
return countLeaves([Link]) + countLeaves([Link]);
}
static int findDiameter(TreeNode r) {
diameter = 0;
heightForDiameter(r);
return diameter;
}
static int heightForDiameter(TreeNode r) {
if (r == null) return -1;
int l = heightForDiameter([Link]);
int ri = heightForDiameter([Link]);
diameter = [Link](diameter, l + ri + 2);
return 1 + [Link](l, ri);
}
static boolean isBalanced(TreeNode r) { return checkHeight(r) != -2; }
static int checkHeight(TreeNode r) {
if (r == null) return -1;
int l = checkHeight([Link]);
if (l == -2) return -2;
int ri = checkHeight([Link]);
if (ri == -2) return -2;
if ([Link](l - ri) > 1) return -2;
return 1 + [Link](l, ri);
}
static boolean isSymmetric(TreeNode r) {
return r == null || isMirror([Link], [Link]);
}
static boolean isMirror(TreeNode l, TreeNode r) {
if (l == null && r == null) return true;
if (l == null || r == null) return false;
return [Link] == [Link] && isMirror([Link], [Link]) &&
isMirror([Link], [Link]);
}
static List<Integer> rightSideView(TreeNode r) {
List<Integer> res = new ArrayList<>();
if (r == null) return res;
Queue<TreeNode> q = new LinkedList<>();
[Link](r);
while (![Link]()) {
int sz = [Link]();
for (int i = 0; i < sz; i++) {
TreeNode n = [Link]();
if (i == sz - 1) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
}
return res;
}
}
13 Practice Problems for Chapter 16
Solve in this order:
Easy Find height of a binary tree
Easy Count total nodes and leaf nodes
Easy Check if two trees are identical
Medium Diameter of binary tree (LeetCode #543)
Medium Check if tree is height-balanced (LeetCode #110)
Medium Right side view of binary tree (LeetCode #199)
Hard Path sum II — print all root-to-leaf paths that equal target
💡 Key Insight: Almost every tree problem is solved with recursion — trust the recursive call to
handle subtrees and focus only on what the current node needs to do. This mental model will
carry you straight into Chapter 17 — Tree Traversals (DFS Pre/In/Post + BFS), which builds
directly on everything you learned here.
Prepared using Claude Sonnet 4.6 Thinking • Java Data Structures & Algorithms Series