Trees
A tree is a family tree: one root, each node has children, no loops. Nearly every tree problem is solved by trusting recursion — "solve the left subtree, solve the right subtree, combine" — or by visiting level by level with a queue.
After this topic: You can write DFS and BFS from memory, decide what each recursive call returns, and combine child answers.
Do these first: Binary Search, Linked List
Step 0 · New to this idea? Warm up first
Solve a problem with a smaller copy of itself: base case, call stack and why recursion can repeat work.
Step 1 · Read the lesson
Recurse on subtrees, or sweep level by level with a queue.
Step 2 · Solve the problems in order
Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.
If both subtrees are already inverted, what is the only thing left to do at this node?
Recursively invert left and right, then swap them.
Target: O(n) time, O(h) space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func invertTree(root *TreeNode) *TreeNodeTested with go test. Try it yourself first, then compare. It is explained step by step on the Trees: BFS / DFS lesson page.
// InvertTree (LeetCode 226): mirror the tree. func InvertTree(root *TreeNode) *TreeNode { if root == nil { return nil } root.Left, root.Right = InvertTree(root.Right), InvertTree(root.Left) return root }The depth of a node is defined using the depths of its children.
1 + max(depth(left), depth(right)); an empty node has depth 0.
Target: O(n) time, O(h) space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func maxDepth(root *TreeNode) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Trees: BFS / DFS lesson page.
// MaxDepth (LeetCode 104): number of nodes on the longest root-to-leaf path. func MaxDepth(root *TreeNode) int { if root == nil { return 0 } return 1 + max(MaxDepth(root.Left), MaxDepth(root.Right)) }The longest path through a node is its left height plus its right height. The best path may not touch the root.
DFS returns the height; at every node update a global best with leftHeight + rightHeight.
Target: O(n) time, O(h) space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func diameterOfBinaryTree(root *TreeNode) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Trees: BFS / DFS lesson page.
// DiameterOfBinaryTree (LeetCode 543): global-variable style. // The function RETURNS the height (what the parent needs) but RECORDS the best // bend through this node in an outer variable (what the question asks). func DiameterOfBinaryTree(root *TreeNode) int { best := 0 var height func(n *TreeNode) int height = func(n *TreeNode) int { if n == nil { return 0 } l, r := height(n.Left), height(n.Right) best = max(best, l+r) // path bending at n uses both sides return 1 + max(l, r) } height(root) return best }Compute height and check balance in the same pass instead of recomputing heights.
DFS returns the height, or −1 as a signal that a subtree is unbalanced; propagate −1 upward.
Target: O(n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func isBalanced(root *TreeNode) boolTested with go test. Try it yourself first, then compare.
// IsBalanced: compute height and check balance in the same pass. A height of -1 means "already unbalanced", // and it is passed up so nothing above recomputes anything. func IsBalanced(root *TreeNode) bool { var height func(*TreeNode) int height = func(n *TreeNode) int { if n == nil { return 0 } l, r := height(n.Left), height(n.Right) if l == -1 || r == -1 || abs(l-r) > 1 { return -1 } return 1 + max(l, r) } return height(root) != -1 } func abs(x int) int { if x < 0 { return -x } return x }Two trees are the same if the roots match and the children trees match.
Both nil → true; one nil → false; values differ → false; else recurse on left pair and right pair.
Target: O(n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func isSameTree(p *TreeNode, q *TreeNode) boolTested with go test. Try it yourself first, then compare.
// IsSameTree: two trees are the same when the roots match and both pairs of subtrees match. func IsSameTree(p, q *TreeNode) bool { if p == nil || q == nil { return p == q // both nil is a match; one nil is not } return p.Val == q.Val && IsSameTree(p.Left, q.Left) && IsSameTree(p.Right, q.Right) }You already wrote "are these two trees identical?". Where could the subtree start?
At every node of the big tree, check sameTree(node, subRoot). Return true if any node matches.
Target: O(n·m) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func isSubtree(root *TreeNode, subRoot *TreeNode) boolTested with go test. Try it yourself first, then compare.
// IsSubtree: subRoot is a subtree if it is identical to the tree starting at SOME node of root. func IsSubtree(root, subRoot *TreeNode) bool { if root == nil { return subRoot == nil } return IsSameTree(root, subRoot) || IsSubtree(root.Left, subRoot) || IsSubtree(root.Right, subRoot) }In a BST, left is smaller and right is bigger. When do p and q stop going the same direction?
Start at root: if both values are smaller go left, if both bigger go right, otherwise the current node is the LCA.
Target: O(h) time, O(1) space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNodeTested with go test. Try it yourself first, then compare.
// LowestCommonAncestorBST uses the BST ordering: if both values are smaller go left, if both are larger go right. // The first node where they split (or equal one of them) is the lowest common ancestor. func LowestCommonAncestorBST(root, p, q *TreeNode) *TreeNode { for root != nil { switch { case p.Val < root.Val && q.Val < root.Val: root = root.Left case p.Val > root.Val && q.Val > root.Val: root = root.Right default: return root } } return nil }Visit nodes row by row. What data structure hands you nodes in the order they were discovered?
BFS with a queue; each round process exactly len(queue) nodes — that is one level.
Target: O(n) time, O(w) space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func levelOrder(root *TreeNode) [][]intTested with go test. Try it yourself first, then compare. It is explained step by step on the Trees: BFS / DFS lesson page.
// LevelOrder (LeetCode 102): BFS with a queue, one level per outer iteration. func LevelOrder(root *TreeNode) [][]int { res := [][]int{} if root == nil { return res } queue := []*TreeNode{root} for len(queue) > 0 { size := len(queue) // freeze: exactly these nodes belong to this level level := make([]int, 0, size) for i := 0; i < size; i++ { n := queue[0] queue = queue[1:] level = append(level, n.Val) if n.Left != nil { queue = append(queue, n.Left) } if n.Right != nil { queue = append(queue, n.Right) } } res = append(res, level) } return res }What do you see from the right? Exactly one node per level.
Level-order BFS and keep the last node of each level.
Target: O(n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func rightSideView(root *TreeNode) []intTested with go test. Try it yourself first, then compare.
// RightSideView: from the right you see exactly one node per level, the last one in that level. func RightSideView(root *TreeNode) []int { out := []int{} if root == nil { return out } queue := []*TreeNode{root} for len(queue) > 0 { size := len(queue) // everything currently in the queue is one level for i := 0; i < size; i++ { n := queue[0] queue = queue[1:] if i == size-1 { out = append(out, n.Val) } if n.Left != nil { queue = append(queue, n.Left) } if n.Right != nil { queue = append(queue, n.Right) } } } return out }A node is good based on the path from the root. What information do you carry down?
DFS passing the maximum value seen on the path; if node ≥ max it is good; pass max(max, node) to children.
Target: O(n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func goodNodes(root *TreeNode) intTested with go test. Try it yourself first, then compare.
// GoodNodes: a node is good if no node on the path from the root is larger. Carry the path maximum downward. func GoodNodes(root *TreeNode) int { var dfs func(n *TreeNode, pathMax int) int dfs = func(n *TreeNode, pathMax int) int { if n == nil { return 0 } count := 0 if n.Val >= pathMax { count = 1 } pathMax = max(pathMax, n.Val) return count + dfs(n.Left, pathMax) + dfs(n.Right, pathMax) } if root == nil { return 0 } return dfs(root, root.Val) }Checking only parent vs child is not enough — every node in the left subtree must be smaller than the root.
DFS with an allowed range (low, high); going left tightens high to node.val, going right tightens low. (Or inorder must be strictly increasing.)
Target: O(n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func isValidBST(root *TreeNode) boolTested with go test. Try it yourself first, then compare. It is explained step by step on the Trees: BFS / DFS lesson page.
// IsValidBST (LeetCode 98): pass the allowed (lo, hi) range down, not just the parent. // nil bounds mean "unbounded", which also handles Val == MinInt/MaxInt safely. func IsValidBST(root *TreeNode) bool { var check func(n *TreeNode, lo, hi *int) bool check = func(n *TreeNode, lo, hi *int) bool { if n == nil { return true } if (lo != nil && n.Val <= *lo) || (hi != nil && n.Val >= *hi) { return false } return check(n.Left, lo, &n.Val) && check(n.Right, &n.Val, hi) } return check(root, nil, nil) }What traversal order of a BST visits values from smallest to largest?
Inorder traversal (left, node, right), counting visited nodes; stop at the k-th.
Target: O(h + k) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func kthSmallest(root *TreeNode, k int) intTested with go test. Try it yourself first, then compare.
// KthSmallest: an inorder walk (left, node, right) of a BST visits values in increasing order, // so stop at the k-th visited node. func KthSmallest(root *TreeNode, k int) int { var stack []*TreeNode cur := root for cur != nil || len(stack) > 0 { for cur != nil { stack = append(stack, cur) // go as far left as possible cur = cur.Left } cur = stack[len(stack)-1] stack = stack[:len(stack)-1] if k--; k == 0 { return cur.Val } cur = cur.Right } return -1 }The first preorder value is always the root. Where does that value sit in inorder, and what does it split?
Root = preorder[0]; find its index in inorder (use a map) → size of the left subtree; recurse on the matching slices.
Target: O(n) time with an index map
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func buildTree(preorder []int, inorder []int) *TreeNodeTested with go test. Try it yourself first, then compare.
// BuildTree: preorder[0] is the root. Its position in inorder splits the other values into the left and // right subtrees, and the left subtree's size tells you where its preorder values end. func BuildTree(preorder, inorder []int) *TreeNode { pos := make(map[int]int, len(inorder)) // value -> index in inorder for i, v := range inorder { pos[v] = i } next := 0 // next unused index of preorder var build func(lo, hi int) *TreeNode // builds the subtree covering inorder[lo..hi] build = func(lo, hi int) *TreeNode { if lo > hi { return nil } root := &TreeNode{Val: preorder[next]} next++ mid := pos[root.Val] root.Left = build(lo, mid-1) // preorder visits the whole left subtree before the right one root.Right = build(mid+1, hi) return root } return build(0, len(inorder)-1) }A path can bend at a node, but a parent can only extend a straight leg. Negative legs should be ignored.
DFS returns the best downward gain (node + max(left,0,right,0)); at each node update the global answer with node + leftGain + rightGain.
Target: O(n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func maxPathSum(root *TreeNode) intTested with go test. Try it yourself first, then compare.
// MaxPathSum: a path may bend at one node, but a parent can only extend a straight leg downward. // Each call returns its best downward leg (ignoring negative legs); the bent path through a node is // node + left leg + right leg, and the best of those over all nodes is the answer. func MaxPathSum(root *TreeNode) int { best := -1 << 60 var leg func(*TreeNode) int leg = func(n *TreeNode) int { if n == nil { return 0 } l, r := max(leg(n.Left), 0), max(leg(n.Right), 0) best = max(best, n.Val+l+r) return n.Val + max(l, r) } leg(root) return best }Write nil children explicitly so the structure can be rebuilt unambiguously.
Preorder DFS to a comma-separated string with "N" for nil; deserialize by reading tokens in the same order recursively.
Target: O(n) time and space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func (c *Codec) serialize(root *TreeNode) string func (c *Codec) deserialize(data string) *TreeNodeTested with go test. Try it yourself first, then compare.
// Serialize writes the tree in preorder with "N" for a missing child, so the shape is unambiguous. func Serialize(root *TreeNode) string { var parts []string var walk func(*TreeNode) walk = func(n *TreeNode) { if n == nil { parts = append(parts, "N") return } parts = append(parts, strconv.Itoa(n.Val)) walk(n.Left) walk(n.Right) } walk(root) return strings.Join(parts, ",") } // Deserialize reads the same tokens in the same order: each call consumes one token, then its two subtrees. func Deserialize(data string) *TreeNode { tokens := strings.Split(data, ",") i := 0 var build func() *TreeNode build = func() *TreeNode { tok := tokens[i] i++ if tok == "N" { return nil } v, _ := strconv.Atoi(tok) return &TreeNode{Val: v, Left: build(), Right: build()} } return build() }