Tree Problems
Let's solve classic tree problems that frequently appear in interviews.
1. Height of a Binary Tree
Recursively compute max height of left and right + 1.
public int height(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(height(root.left), height(root.right));
}
2. Diameter of Binary Tree
Longest path between any two nodes. Can be computed as max(left height + right height) across all nodes.
int maxDiameter = 0;
public int diameter(TreeNode root) {
heightForDiameter(root);
return maxDiameter;
}
private int heightForDiameter(TreeNode root) {
if (root == null) return 0;
int left = heightForDiameter(root.left);
int right = heightForDiameter(root.right);
maxDiameter = Math.max(maxDiameter, left + right);
return 1 + Math.max(left, right);
}
3. Check if Tree is Balanced
A tree is balanced if for every node, height difference ≤ 1.
Two Minute Drill
- Height: O(n) recursion.
- Diameter: O(n) postorder, compute path lengths.
- Balanced tree check: compute height and compare difference.
- These problems are fundamental for tree interviews.
Need more clarification?
Drop us an email at career@quipoinfotech.com