Recursive Strategies: Traversal vs. Divide and Conquer
Recursive solutions for binary trees typically fall into two categories:
- Traversal (Top-Down): The result is passed as a parameter during the recursive calls. The logic processes the node and propagates data downwards.
- Divide and Conquer (Bottom-Up): The result is returned by the function. The problem is broken down into smaller subproblems (left and right subtrees), and the results are combined upon returning. This approach is effective for the majority of binary tree problems.
The time complexity for tree analysis is generally calculated as the total number of nodes multiplied by the processing time per node.
Binary Tree Node Structure
The fundamental structure for a binary tree node typically contains a value and references to left and right children.
public class TreeNode {
public int value;
public TreeNode leftChild, rightChild;
public TreeNode(int val) {
this.value = val;
this.leftChild = this.rightChild = null;
}
}
Tree Traversals
Recursive Implementations
Recursive traversals are straightforward, following the specific order of node processing.
Pre-order (Root - Left - Right):
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
traversePreorder(root, result);
return result;
}
private void traversePreorder(TreeNode node, List<Integer> list) {
if (node == null) return;
list.add(node.value);
traversePreorder(node.leftChild, list);
traversePreorder(node.rightChild, list);
}
In-order (Left - Root - Right):
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
traverseInorder(root, result);
return result;
}
private void traverseInorder(TreeNode node, List<Integer> list) {
if (node == null) return;
traverseInorder(node.leftChild, list);
list.add(node.value);
traverseInorder(node.rightChild, list);
}
Post-order (Left - Right - Root):
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
result.addAll(postorderTraversal(root.leftChild));
result.addAll(postorderTraversal(root.rightChild));
result.add(root.value);
return result;
}
Iterative Implementations
Iterative approaches use an explicit stack to simulate the recursion call stack.
Pre-order:
public List<Integer> preorderIterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode current = stack.pop();
result.add(current.value);
if (current.rightChild != null) stack.push(current.rightChild);
if (current.leftChild != null) stack.push(current.leftChild);
}
return result;
}
In-order:
public List<Integer> inorderIterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.leftChild;
}
current = stack.pop();
result.add(current.value);
current = current.rightChild;
}
return result;
}
Post-order:
public List<Integer> postorderIterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
TreeNode lastVisited = null;
while (!stack.isEmpty()) {
TreeNode current = stack.peek();
// Traverse down the tree
if (lastVisited == null || lastVisited.leftChild == current || lastVisited.rightChild == current) {
if (current.leftChild != null) {
stack.push(current.leftChild);
} else if (current.rightChild != null) {
stack.push(current.rightChild);
}
// Returning from left child
} else if (current.leftChild == lastVisited) {
if (current.rightChild != null) {
stack.push(current.rightChild);
}
// Returning from right child (process node)
} else {
result.add(current.value);
stack.pop();
}
lastVisited = current;
}
return result;
}
Common Algorithmic Problems
Maximum Depth
Divide and Conquer Approach:
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int leftDepth = maxDepth(root.leftChild);
int rightDepth = maxDepth(root.rightChild);
return Math.max(leftDepth, rightDepth) + 1;
}
Traversal Approach:
private int maxDepth;
public int maxDepthTraversal(TreeNode root) {
maxDepth = 0;
calculateDepth(root, 1);
return maxDepth;
}
private void calculateDepth(TreeNode node, int currentDepth) {
if (node == null) return;
maxDepth = Math.max(maxDepth, currentDepth);
calculateDepth(node.leftChild, currentDepth + 1);
calculateDepth(node.rightChild, currentDepth + 1);
}
Binary Tree Paths
Finding all root-to-leaf paths.
Divide and Conquer:
public List<String> getBinaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
if (root == null) return paths;
List<String> leftPaths = getBinaryTreePaths(root.leftChild);
List<String> rightPaths = getBinaryTreePaths(root.rightChild);
for (String path : leftPaths) {
paths.add(root.value + "->" + path);
}
for (String path : rightPaths) {
paths.add(root.value + "->" + path);
}
if (paths.isEmpty()) {
paths.add(String.valueOf(root.value));
}
return paths;
}
Minimum Subtree
Finding the subtree with the minimum sum.
private TreeNode minSubtreeNode = null;
private int minSum = Integer.MAX_VALUE;
public TreeNode findSubtree(TreeNode root) {
calculateSum(root);
return minSubtreeNode;
}
private int calculateSum(TreeNode node) {
if (node == null) return 0;
int sum = calculateSum(node.leftChild) + calculateSum(node.rightChild) + node.value;
if (sum < minSum) {
minSum = sum;
minSubtreeNode = node;
}
return sum;
}
Balanced Binary Tree
Determining if a tree is height-balanced using a ResultType for efficiency (O(N)).
class BalanceResult {
public boolean isBalanced;
public int height;
public BalanceResult(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
}
public boolean isBalanced(TreeNode root) {
return checkBalance(root).isBalanced;
}
private BalanceResult checkBalance(TreeNode node) {
if (node == null) {
return new BalanceResult(true, 0);
}
BalanceResult left = checkBalance(node.leftChild);
BalanceResult right = checkBalance(node.rightChild);
if (!left.isBalanced || !right.isBalanced) {
return new BalanceResult(false, -1);
}
if (Math.abs(left.height - right.height) > 1) {
return new BalanceResult(false, -1);
}
return new BalanceResult(true, Math.max(left.height, right.height) + 1);
}
Lowest Common Ancestor (LCA)
Assuming both nodes exist in the tree.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
if (root == null || root == A || root == B) {
return root;
}
TreeNode left = lowestCommonAncestor(root.leftChild, A, B);
TreeNode right = lowestCommonAncestor(root.rightChild, A, B);
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
if (right != null) {
return right;
}
return null;
}
Binary Search Tree (BST)
Properties
A BST is defined by the property that for every node, all values in the left subtree are smaller than the node's value, and all values in the right subtree are greater. An in-order traversal of a valid BST yields a strictly increasing sequence.
Validate BST
Using a range-based recursive approach.
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.value <= min || node.value >= max) {
return false;
}
return validate(node.leftChild, min, node.value) &&
validate(node.rightChild, node.value, max);
}