Master hierarchical data structures. Learn tree terminology, binary tree properties, tree traversals, BST operations, and balanced variants. Includes 15+ fully solved LeetCode problems with complete C# implementations and interview strategies.
A tree is a non-linear, hierarchical data structure consisting of nodes connected by edges. Unlike arrays or linked lists, trees enable efficient searching and organizing of hierarchical data.
Understanding tree vocabulary is essential for communication and problem-solving:
| Term | Definition | Example | ||
|---|---|---|---|---|
| Root | The topmost node with no parent | Node with value 1 in a typical tree diagram | ||
| Leaf | Node with no children | All terminal nodes | ||
| Parent | Node directly above another node | In binary tree, a node can have 0-2 parents | ||
| Child | Node directly below a parent | Left child, right child in binary trees | ||
| Sibling | Nodes sharing the same parent | Left and right children are siblings | ||
| Subtree | A tree formed by a node and its descendants | Left subtree, right subtree | ||
| Ancestor | Any node on the path from node to root | All nodes above current node | ||
| Descendant | Any node in a node's subtree | All nodes below current node | ||
| Depth | Distance from root to a node (number of edges) | |||
| Rotation Type | Imbalance Pattern | Fix | ||
| LL (Left-Left) | Left subtree too deep on left | Single right rotation | ||
| RR (Right-Right) | Right subtree too deep on right | Single left rotation | ||
| LR (Left-Right) | Left subtree too deep on right | Left-right rotation (two rotations) | ||
| RL (Right-Left) | Right subtree too deep on left | Right-left rotation (two rotations) |
Alternative balanced BST with color-based properties:
Use these for automatic balancing instead of manual implementation:
// Automatically balanced BST in C# var set = new SortedSet<int>(); set.Add(5); set.Add(3); set.Add(7); // O(log n) operations bool contains = set.Contains(3); // true // Get all elements >= value var view = set.GetViewBetween(3, 7); // Sorted dictionary for key-value pairs var dict = new SortedDictionary<int, string>(); dict[3] = "three"; dict[1] = "one";
Recurring problem templates that guide solution design. Recognize these patterns to solve problems faster.
The classic pattern for tree recursion:
// Base recursive template private ResultType DfsHelper(TreeNode node) { // 1. Base case if (node == null) return defaultValue; // 2. Pre-order work (before recursion) // Process current node // 3. Recurse on children ResultType left = DfsHelper(node.left); ResultType right = DfsHelper(node.right); // 4. Post-order work (after recursion) // Combine results, return return result; }
Accumulate values while traversing from root to leaves:
// Accumulator pattern for paths private void DfsPath(TreeNode node, int currentSum, List<int> path) { if (node == null) return; // Add current node to path path.Add(node.val); currentSum += node.val; // Check if leaf and condition met if (node.left == null && node.right == null) { if (currentSum == targetSum) result.Add(new List<int>(path)); } // Recurse DfsPath(node.left, currentSum, path); DfsPath(node.right, currentSum, path); // Backtrack path.RemoveAt(path.Count - 1); }
15+ fully solved LeetCode problems with complete C# implementations and detailed explanations.
Approach: Recursively find height of left and right subtrees, return 1 + max of both.
public class Solution { public int MaxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right)); } }
Approach: Key: a path to a leaf must have both children null. Don't count unary nodes.
public class Solution { public int MinDepth(TreeNode root) { if (root == null) return 0; // Leaf node if (root.left == null && root.right == null) return 1; // Skip unary nodes - they don't count as leaf if (root.left == null) return 1 + MinDepth(root.right); if (root.right == null) return 1 + MinDepth(root.left); return 1 + Math.Min(MinDepth(root.left), MinDepth(root.right)); } }
Approach: Track valid min/max range for each subtree. Node must be within bounds.
public class Solution { public bool IsValidBST(TreeNode root) { return Validate(root, null, null); } private bool Validate(TreeNode node, TreeNode min, TreeNode max) { if (node == null) return true; if (min != null && node.val <= min.val) return false; if (max != null && node.val >= max.val) return false; // Left subtree: values < node.val if (!Validate(node.left, min, node)) return false; // Right subtree: values > node.val return Validate(node.right, node, max); } }
Approach: Compare left and right subtrees recursively, checking mirror positions.
public class Solution { public bool IsSymmetric(TreeNode root) { return IsMirror(root.left, root.right); } private bool IsMirror(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if (left == null || right == null) return false; return left.val == right.val && IsMirror(left.left, right.right) && IsMirror(left.right, right.left); } }
Approach: Use queue, process all nodes at current level before moving to next.
public class Solution { public IList<IList<int>> LevelOrder(TreeNode root) { var result = new List<IList<int>>(); if (root == null) return result; var queue = new Queue<TreeNode>(); queue.Enqueue(root); while (queue.Count > 0) { int levelSize = queue.Count; var level = new List<int>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.Dequeue(); level.Add(node.val); if (node.left != null) queue.Enqueue(node.left); if (node.right != null) queue.Enqueue(node.right); } result.Add(level); } return result; } }
Approach: Same as level order but reverse every other level using a flag.
public class Solution { public IList<IList<int>> ZigzagLevelOrder(TreeNode root) { var result = new List<IList<int>>(); if (root == null) return result; var queue = new Queue<TreeNode>(); queue.Enqueue(root); bool leftToRight = true; while (queue.Count > 0) { int levelSize = queue.Count; var level = new List<int>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.Dequeue(); level.Add(node.val); if (node.left != null) queue.Enqueue(node.left); if (node.right != null) queue.Enqueue(node.right); } if (!leftToRight) level.Reverse(); result.Add(level); leftToRight = !leftToRight; } return result; } }
Approach: Use BST property. If both p,q < node, go left. If both > node, go right. Otherwise, node is LCA.
public class Solution { public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (root != null) { if (p.val < root.val && q.val < root.val) root = root.left; else if (p.val > root.val && q.val > root.val) root = root.right; else return root; } return root; } }
Approach: Recursively search left and right. If both return non-null, current is LCA.
public class Solution { public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode left = LowestCommonAncestor(root.left, p, q); TreeNode right = LowestCommonAncestor(root.right, p, q); if (left != null && right != null) return root; return left != null ? left : right; } }
Approach: Simple recursive swap at each node.
public class Solution { public TreeNode InvertTree(TreeNode root) { if (root == null) return null; // Swap TreeNode temp = root.left; root.left = root.right; root.right = temp; // Recurse InvertTree(root.left); InvertTree(root.right); return root; } }
Approach: DFS accumulating sum. Check at leaf nodes.
public class Solution { public bool HasPathSum(TreeNode root, int targetSum) { if (root == null) return false; // Subtract current value from target targetSum -= root.val; // Check leaf if (root.left == null && root.right == null) return targetSum == 0; return HasPathSum(root.left, targetSum) || HasPathSum(root.right, targetSum); } }
Approach: DFS with path accumulator and backtracking.
public class Solution { public IList<IList<int>> PathSum(TreeNode root, int targetSum) { var result = new List<IList<int>>(); Dfs(root, targetSum, new List<int>(), result); return result; } private void Dfs(TreeNode node, int sum, List<int> path, IList<IList<int>> result) { if (node == null) return; path.Add(node.val); sum -= node.val; if (node.left == null && node.right == null && sum == 0) result.Add(new List<int>(path)); Dfs(node.left, sum, path, result); Dfs(node.right, sum, path, result); path.RemoveAt(path.Count - 1); // Backtrack } }
Approach: Inorder traversal visits values in sorted order. Stop at kth element.
public class Solution { int count = 0; int result = 0; public int KthSmallest(TreeNode root, int k) { Inorder(root, k); return result; } private void Inorder(TreeNode node, int k) { if (node == null) return; Inorder(node.left, k); count++; if (count == k) { result = node.val; return; } Inorder(node.right, k); } }
Approach: Level order traversal, keep last node of each level.
public class Solution { public IList<int> RightSideView(TreeNode root) { var result = new List<int>(); if (root == null) return result; var queue = new Queue<TreeNode>(); queue.Enqueue(root); while (queue.Count > 0) { int levelSize = queue.Count; TreeNode rightmost = null; for (int i = 0; i < levelSize; i++) { rightmost = queue.Dequeue(); if (rightmost.left != null) queue.Enqueue(rightmost.left); if (rightmost.right != null) queue.Enqueue(rightmost.right); } result.Add(rightmost.val); } return result; } }
Approach: For each node, diameter = left height + right height. Track maximum.
public class Solution { int diameter = 0; public int DiameterOfBinaryTree(TreeNode root) { Height(root); return diameter; } private int Height(TreeNode node) { if (node == null) return 0; int left = Height(node.left); int right = Height(node.right); diameter = Math.Max(diameter, left + right); return 1 + Math.Max(left, right); } }
Approach: Postorder traversal, connect nodes while returning to parents.
public class Solution { TreeNode prev = null; public void Flatten(TreeNode root) { if (root == null) return; // Reverse preorder: Root, Right, Left Flatten(root.right); Flatten(root.left); // Connect current to prev (which is next in preorder) root.right = prev; root.left = null; prev = root; } }