Trees — The Complete Visual Reference

class TreeNode( var `val`: Int, var left: TreeNode? = null, var right: TreeNode? = null )

// Inorder: left → root → right fun inorder(node: TreeNode?, result: MutableList<Int>) { if (node == null) return inorder(node.left, result) result.add(node.`val`) inorder(node.right, result) } // Preorder: root → left → right fun preorder(node: TreeNode?, result: MutableList<Int>) { if (node == null) return result.add(node.`val`) preorder(node.left, result) preorder(node.right, result) } // Postorder: left → right → root fun postorder(node: TreeNode?, result: MutableList<Int>) { if (node == null) return postorder(node.left, result) postorder(node.right, result) result.add(node.`val`) }

fun levelOrder(root: TreeNode?): List<Int> { if (root == null) return emptyList() val result = mutableListOf<Int>() val queue: Queue<TreeNode> = LinkedList() queue.add(root) while (queue.isNotEmpty()) { val node = queue.poll() result.add(node.`val`) node.left?.let { queue.add(it) } node.right?.let { queue.add(it) } } return result } // Grouped by level fun levelOrderGrouped(root: TreeNode?): List<List<Int>> { if (root == null) return emptyList() val result = mutableListOf<List<Int>>() val queue: Queue<TreeNode> = LinkedList() queue.add(root) while (queue.isNotEmpty()) { val size = queue.size // snapshot! val level = mutableListOf<Int>() repeat(size) { val node = queue.poll() level.add(node.`val`) node.left?.let { queue.add(it) } node.right?.let { queue.add(it) } } result.add(level) } return result }

// Inorder iterative fun inorderIterative(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() val stack = ArrayDeque<TreeNode>() var cur = root while (cur != null || stack.isNotEmpty()) { while (cur != null) { stack.addFirst(cur) cur = cur.left // push all left } cur = stack.removeFirst() result.add(cur.`val`) // visit cur = cur.right // go right } return result } // Preorder iterative fun preorderIterative(root: TreeNode?): List<Int> { if (root == null) return emptyList() val result = mutableListOf<Int>() val stack = ArrayDeque<TreeNode>() stack.addFirst(root) while (stack.isNotEmpty()) { val node = stack.removeFirst() result.add(node.`val`) node.right?.let { stack.addFirst(it) } node.left?.let { stack.addFirst(it) } } return result } // Postorder iterative (modified preorder + reverse) fun postorderIterative(root: TreeNode?): List<Int> { if (root == null) return emptyList() val result = LinkedList<Int>() val stack = ArrayDeque<TreeNode>() stack.addFirst(root) while (stack.isNotEmpty()) { val node = stack.removeFirst() result.addFirst(node.`val`) node.left?.let { stack.addFirst(it) } node.right?.let { stack.addFirst(it) } } return result }

fun morrisInorder(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() var cur = root while (cur != null) { if (cur.left == null) { result.add(cur.`val`) cur = cur.right } else { var pred = cur.left!! while (pred.right != null && pred.right != cur) pred = pred.right!! if (pred.right == null) { pred.right = cur // create thread cur = cur.left } else { pred.right = null // remove thread result.add(cur.`val`) cur = cur.right } } } return result }

// Search (iterative) fun searchBST(root: TreeNode?, target: Int): TreeNode? { var node = root while (node != null) { node = when { target < node.`val` -> node.left target > node.`val` -> node.right else -> return node } } return null } // Insert fun insertBST(root: TreeNode?, v: Int): TreeNode { if (root == null) return TreeNode(v) if (v < root.`val`) root.left = insertBST(root.left, v) else root.right = insertBST(root.right, v) return root } // Delete (3 cases) fun deleteBST(root: TreeNode?, key: Int): TreeNode? { if (root == null) return null if (key < root.`val`) root.left = deleteBST(root.left, key) else if (key > root.`val`) root.right = deleteBST(root.right, key) else { if (root.left == null) return root.right // case 1 & 2 if (root.right == null) return root.left val succ = findMin(root.right!!) // case 3 root.`val` = succ.`val` root.right = deleteBST(root.right, succ.`val`) } return root }

fun findMin(node: TreeNode): TreeNode { var cur = node while (cur.left != null) cur = cur.left!! return cur } fun findMax(node: TreeNode): TreeNode { var cur = node while (cur.right != null) cur = cur.right!! return cur }

// Correct: check with min/max bounds fun isValidBST(root: TreeNode?): Boolean { fun validate(node: TreeNode?, min: Long, max: Long): Boolean { if (node == null) return true if (node.`val` <= min || node.`val` >= max) return false return validate(node.left, min, node.`val`.toLong()) && validate(node.right, node.`val`.toLong(), max) } return validate(root, Long.MIN_VALUE, Long.MAX_VALUE) } // WRONG: only checks immediate children fun isValidBSTWrong(node: TreeNode?): Boolean { if (node == null) return true if (node.left != null && node.left!!.`val` >= node.`val`) return false // ✗ Misses: grandchild could violate ancestor constraint return isValidBSTWrong(node.left) && isValidBSTWrong(node.right) }

// TreeMap — sorted key-value store val map = TreeMap<Int, String>() map[5] = "five"; map[2] = "two"; map[8] = "eight" map.firstKey() // 2 map.lastKey() // 8 map.higherKey(5) // 8 (strictly greater) map.lowerKey(5) // 2 (strictly less) map.ceilingKey(5) // 5 (≥) map.floorKey(5) // 5 (≤) map.subMap(2, 8) // {2=two, 5=five} [2, 8) map.headMap(5) // {2=two} [first, 5) map.tailMap(5) // {5=five, 8=eight} [5, last] // TreeSet — sorted set val set = TreeSet<Int>() set.addAll(listOf(5, 2, 8, 1)) set.first() // 1 set.last() // 8 set.higher(2) // 5 set.lower(5) // 2 set.ceiling(3) // 5 set.floor(3) // 2 set.subSet(2, 8) // [2, 5]

fun maxDepth(root: TreeNode?): Int { if (root == null) return 0 return maxOf(maxDepth(root.left), maxDepth(root.right)) + 1 } fun minDepth(root: TreeNode?): Int { if (root == null) return 0 val l = minDepth(root.left) val r = minDepth(root.right) if (l == 0 || r == 0) return l + r + 1 // single-child case return minOf(l, r) + 1 } fun minDepthBFS(root: TreeNode?): Int { if (root == null) return 0 val queue: Queue<TreeNode> = LinkedList() queue.add(root) var depth = 0 while (queue.isNotEmpty()) { depth++ repeat(queue.size) { val node = queue.poll() if (node.left == null && node.right == null) return depth node.left?.let { queue.add(it) } node.right?.let { queue.add(it) } } } return depth }

fun diameterOfBinaryTree(root: TreeNode?): Int { var maxDiam = 0 fun height(node: TreeNode?): Int { if (node == null) return 0 val l = height(node.left) val r = height(node.right) maxDiam = maxOf(maxDiam, l + r) return maxOf(l, r) + 1 } height(root) return maxDiam }

fun isBalanced(root: TreeNode?): Boolean { fun check(node: TreeNode?): Int { if (node == null) return 0 val l = check(node.left); if (l == -1) return -1 val r = check(node.right); if (r == -1) return -1 if (Math.abs(l - r) > 1) return -1 return maxOf(l, r) + 1 } return check(root) != -1 } fun isSymmetric(root: TreeNode?): Boolean { fun isMirror(a: TreeNode?, b: TreeNode?): Boolean { if (a == null && b == null) return true if (a == null || b == null) return false return a.`val` == b.`val` && isMirror(a.left, b.right) && isMirror(a.right, b.left) } return isMirror(root?.left, root?.right) }

fun invertTree(root: TreeNode?): TreeNode? { if (root == null) return null val tmp = root.left root.left = invertTree(root.right) root.right = invertTree(tmp) return root } // Iterative BFS version fun invertTreeIterative(root: TreeNode?): TreeNode? { if (root == null) return null val queue: Queue<TreeNode> = LinkedList() queue.add(root) while (queue.isNotEmpty()) { val node = queue.poll() val tmp = node.left node.left = node.right node.right = tmp node.left?.let { queue.add(it) } node.right?.let { queue.add(it) } } return root }

// Path Sum I: root-to-leaf fun hasPathSum(root: TreeNode?, target: Int): Boolean { if (root == null) return false if (root.left == null && root.right == null) return root.`val` == target val rem = target - root.`val` return hasPathSum(root.left, rem) || hasPathSum(root.right, rem) } // Path Sum II: all root-to-leaf paths (backtracking) fun pathSum(root: TreeNode?, target: Int): List<List<Int>> { val result = mutableListOf<List<Int>>() fun dfs(node: TreeNode?, rem: Int, path: MutableList<Int>) { if (node == null) return path.add(node.`val`) if (node.left == null && node.right == null && rem == node.`val`) result.add(ArrayList(path)) dfs(node.left, rem - node.`val`, path) dfs(node.right, rem - node.`val`, path) path.removeAt(path.size - 1) // backtrack } dfs(root, target, mutableListOf()) return result } // Path Sum III: any-start/end (prefix sum + HashMap) fun pathSumIII(root: TreeNode?, target: Long): Int { val prefixMap = HashMap<Long, Int>() prefixMap[0L] = 1 var count = 0 fun dfs(node: TreeNode?, curSum: Long) { if (node == null) return val sum = curSum + node.`val` count += prefixMap.getOrDefault(sum - target, 0) prefixMap[sum] = prefixMap.getOrDefault(sum, 0) + 1 dfs(node.left, sum) dfs(node.right, sum) prefixMap[sum] = prefixMap[sum]!! - 1 // backtrack } dfs(root, 0L) return count }

// Binary tree LCA — O(n) fun lowestCommonAncestor( root: TreeNode?, p: TreeNode, q: TreeNode ): TreeNode? { if (root == null || root == p || root == q) return root val left = lowestCommonAncestor(root.left, p, q) val right = lowestCommonAncestor(root.right, p, q) if (left != null && right != null) return root return left ?: right } // BST LCA — O(h) fun lcaBST(root: TreeNode?, p: TreeNode, q: TreeNode): TreeNode? { var node = root while (node != null) { node = when { p.`val` < node.`val` && q.`val` < node.`val` -> node.left p.`val` > node.`val` && q.`val` > node.`val` -> node.right else -> return node // split point } } return null }

class Codec { fun serialize(root: TreeNode?): String { val sb = StringBuilder() fun preorder(node: TreeNode?) { if (node == null) { sb.append("#,"); return } sb.append("${node.`val`},") preorder(node.left) preorder(node.right) } preorder(root) return sb.toString() } fun deserialize(data: String): TreeNode? { val queue: Queue<String> = LinkedList(data.split(",")) fun build(): TreeNode? { val token = queue.poll() ?: return null if (token == "#") return null val node = TreeNode(token.toInt()) node.left = build() node.right = build() return node } return build() } }

fun buildTreeFromPreIn( preorder: IntArray, inorder: IntArray ): TreeNode? { val inMap = HashMap<Int, Int>() inorder.forEachIndexed { i, v -> inMap[v] = i } var preIdx = 0 fun build(lo: Int, hi: Int): TreeNode? { if (lo > hi) return null val rootVal = preorder[preIdx++] val node = TreeNode(rootVal) val mid = inMap[rootVal]!! node.left = build(lo, mid - 1) node.right = build(mid + 1, hi) return node } return build(0, inorder.size - 1) }

fun rightSideView(root: TreeNode?): List<Int> { if (root == null) return emptyList() val result = mutableListOf<Int>() val queue: Queue<TreeNode> = LinkedList() queue.add(root) while (queue.isNotEmpty()) { val size = queue.size repeat(size) { i -> val node = queue.poll() if (i == size - 1) result.add(node.`val`) node.left?.let { queue.add(it) } node.right?.let { queue.add(it) } } } return result } fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> { if (root == null) return emptyList() val result = mutableListOf<List<Int>>() val queue: Queue<TreeNode> = LinkedList() queue.add(root) var leftToRight = true while (queue.isNotEmpty()) { val level = LinkedList<Int>() repeat(queue.size) { val node = queue.poll() if (leftToRight) level.addLast(node.`val`) else level.addFirst(node.`val`) node.left?.let { queue.add(it) } node.right?.let { queue.add(it) } } result.add(level) leftToRight = !leftToRight } return result }

fun flatten(root: TreeNode?) { var cur = root while (cur != null) { if (cur.left != null) { // Find rightmost of left subtree var pred = cur.left!! while (pred.right != null) pred = pred.right!! // Connect to right subtree pred.right = cur.right // Move left to right cur.right = cur.left cur.left = null } cur = cur.right } }

fun kthSmallest(root: TreeNode?, k: Int): Int { val stack = ArrayDeque<TreeNode>() var cur = root var count = 0 while (cur != null || stack.isNotEmpty()) { while (cur != null) { stack.addFirst(cur); cur = cur.left } cur = stack.removeFirst() if (++count == k) return cur.`val` cur = cur.right } return -1 } class BSTIterator(root: TreeNode?) { private val stack = ArrayDeque<TreeNode>() init { pushLeft(root) } private fun pushLeft(node: TreeNode?) { var n = node while (n != null) { stack.addFirst(n); n = n.left } } fun hasNext(): Boolean = stack.isNotEmpty() fun next(): Int { val node = stack.removeFirst() pushLeft(node.right) return node.`val` } }

fun maxPathSum(root: TreeNode?): Int { var maxSum = Int.MIN_VALUE fun gain(node: TreeNode?): Int { if (node == null) return 0 val l = maxOf(0, gain(node.left)) // ignore negatives val r = maxOf(0, gain(node.right)) maxSum = maxOf(maxSum, l + r + node.`val`) // use both return maxOf(l, r) + node.`val` // contribute one } gain(root) return maxSum } fun goodNodes(root: TreeNode?): Int { fun dfs(node: TreeNode?, maxSoFar: Int): Int { if (node == null) return 0 val good = if (node.`val` >= maxSoFar) 1 else 0 val newMax = maxOf(maxSoFar, node.`val`) return good + dfs(node.left, newMax) + dfs(node.right, newMax) } return dfs(root, Int.MIN_VALUE) }

fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean { if (p == null && q == null) return true if (p == null || q == null) return false return p.`val` == q.`val` && isSameTree(p.left, q.left) && isSameTree(p.right, q.right) } fun isSubtree(root: TreeNode?, sub: TreeNode?): Boolean { if (root == null) return sub == null return isSameTree(root, sub) || isSubtree(root.left, sub) || isSubtree(root.right, sub) } fun mergeTrees(t1: TreeNode?, t2: TreeNode?): TreeNode? { if (t1 == null) return t2 if (t2 == null) return t1 t1.`val` += t2.`val` t1.left = mergeTrees(t1.left, t2.left) t1.right = mergeTrees(t1.right, t2.right) return t1 }

fun verticalOrder(root: TreeNode?): List<List<Int>> { if (root == null) return emptyList() val colMap = TreeMap<Int, MutableList<Int>>() val queue: Queue<Pair<TreeNode, Int>> = LinkedList() queue.add(root to 0) while (queue.isNotEmpty()) { val (node, col) = queue.poll() colMap.getOrPut(col) { mutableListOf() }.add(node.`val`) node.left?.let { queue.add(it to col - 1) } node.right?.let { queue.add(it to col + 1) } } return colMap.values.toList() } fun sortedArrayToBST(nums: IntArray): TreeNode? { fun build(lo: Int, hi: Int): TreeNode? { if (lo > hi) return null val mid = lo + (hi - lo) / 2 val node = TreeNode(nums[mid]) node.left = build(lo, mid - 1) node.right = build(mid + 1, hi) return node } return build(0, nums.size - 1) }

class TrieNode { val children = arrayOfNulls<TrieNode>(26) var isEnd = false } class Trie { private val root = TrieNode() fun insert(word: String) { var node = root for (c in word) { val i = c - 'a' if (node.children[i] == null) node.children[i] = TrieNode() node = node.children[i]!! } node.isEnd = true } fun search(word: String): Boolean { val node = findNode(word) return node?.isEnd == true } fun startsWith(prefix: String): Boolean = findNode(prefix) != null private fun findNode(s: String): TrieNode? { var node = root for (c in s) { node = node.children[c - 'a'] ?: return null } return node } fun wordsWithPrefix(prefix: String): List<String> { val result = mutableListOf<String>() val node = findNode(prefix) ?: return result fun collect(n: TrieNode, sb: StringBuilder) { if (n.isEnd) result.add(sb.toString()) for (i in 0..25) { if (n.children[i] != null) { sb.append('a' + i) collect(n.children[i]!!, sb) sb.deleteCharAt(sb.length - 1) } } } collect(node, StringBuilder(prefix)) return result } } // HashMap-based for flexible character sets class TrieMap { val children = HashMap<Char, TrieMap>() var isEnd = false }

class SegmentTree(private val n: Int) { private val tree = IntArray(4 * n) fun build(arr: IntArray, node: Int = 1, s: Int = 0, e: Int = n - 1) { if (s == e) { tree[node] = arr[s]; return } val mid = (s + e) / 2 build(arr, 2 * node, s, mid) build(arr, 2 * node + 1, mid + 1, e) tree[node] = tree[2 * node] + tree[2 * node + 1] } fun query(l: Int, r: Int, node: Int = 1, s: Int = 0, e: Int = n - 1): Int { if (r < s || e < l) return 0 if (l <= s && e <= r) return tree[node] val mid = (s + e) / 2 return query(l, r, 2 * node, s, mid) + query(l, r, 2 * node + 1, mid + 1, e) } fun update(idx: Int, v: Int, node: Int = 1, s: Int = 0, e: Int = n - 1) { if (s == e) { tree[node] = v; return } val mid = (s + e) / 2 if (idx <= mid) update(idx, v, 2 * node, s, mid) else update(idx, v, 2 * node + 1, mid + 1, e) tree[node] = tree[2 * node] + tree[2 * node + 1] } }

class FenwickTree(private val n: Int) { private val tree = IntArray(n + 1) fun update(i: Int, delta: Int) { var idx = i + 1 while (idx <= n) { tree[idx] += delta idx += idx and (-idx) // add lowest set bit } } fun prefixSum(i: Int): Int { var idx = i + 1 var sum = 0 while (idx > 0) { sum += tree[idx] idx -= idx and (-idx) // remove lowest set bit } return sum } fun rangeSum(l: Int, r: Int): Int = prefixSum(r) - if (l > 0) prefixSum(l - 1) else 0 }

// ✗ Height vs depth confusion // Height = edges from node to deepest leaf (bottom-up) // Depth = edges from root to node (top-down) // ✗ Forgetting null root check fun bad(root: TreeNode): Int = root.`val` // NPE if null! fun good(root: TreeNode?): Int = root?.`val` ?: 0 // ✗ Wrong BST validation (only checking parent-child) // Must check entire subtree constraint with bounds // ✗ Integer overflow in BST validation // Use Long.MIN_VALUE / Long.MAX_VALUE for bounds // ✗ Forgetting to backtrack in path problems path.add(node.`val`) dfs(node.left, path) dfs(node.right, path) path.removeAt(path.size - 1) // ← don't forget! // ✗ === vs == for node identity // Use === for reference equality (is it the same node?) // Use == for value equality // ✗ Stack overflow on skewed trees // Use iterative traversal for trees that could be deep // ✗ Modifying tree when you shouldn't // Some problems expect the original tree unchanged // ✗ Assuming inorder = sorted for non-BST trees // Inorder is only sorted for Binary Search Trees