Trees don’t build themselves.
LeetCode 105 shoves preorder and inorder arrays at you—rebuild the binary tree or bust. Simple, right? Ha. It’s recursion’s playground, where rookies trip and “seniors” pretend it’s elegant.
LeetCode 105: What Fresh Hell Is This?
Picture this: preorder spits roots first—left subtree, then right. Inorder? Left, root, right. Mash ‘em together recursively. Root from preorder[0]. Find it in inorder. Split left/right subarrays. Repeat till empty.
Given two arrays representing preorder and inorder traversals of a binary tree, reconstruct and return the original binary tree.
That’s the pitch. Clean. But peek under the hood.
Here’s the code they flaunt:
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder or not inorder:
return None
root_val = preorder.pop(0)
root = TreeNode(root_val)
root_index = inorder.index(root_val)
root.left = self.buildTree(preorder, inorder[:root_index])
root.right = self.buildTree(preorder, inorder[root_index + 1 :])
return root
Pops preorder head. Indexes inorder for split. Recurses. Returns tree. Time: O(n²). Space: O(n). Cute on paper.
But.
That inorder.index(root_val)? Linear scan. Every level. n times. Boom—quadratic hell for n=1000. Interviews love it. Real code? Laughs you out.
Why LeetCode 105’s Solution Sucks
Short answer: laziness. They pop preorder—mutates it, sneaky but fine. But indexing? Amateur hour. No hashmap for root positions. It’s 1995 all over again, before we wised up.
Visualize with TraceLit, their toy. Step through. See the tree sprout. Left subtree from inorder[:index], right from [index+1:]. Preorder advances naturally—post-pop. Elegant? Sure, if n<100.
Here’s the thing. Interviews cap inputs small. LeetCode? n<=3000, but hidden tests spike. Quadratic tanks it. I’ve seen candidates beam, submit, then TLE. Dry humor: their face? Priceless.
Unique twist nobody mentions: this mirrors 1970s LISP tree parsers—pre-hashmap era. Knuth would’ve snorted. We ditched that for O(n) maps decades ago. LeetCode clings like a bad ex.
And popping preorder? Side-effect city. Pure functionalists cringe. Pass indices instead, you cowards.
Is O(n²) Good Enough for Interviews?
Yes. Barely. FAANG gatekeepers want the idea, not perfection. Nail recursion, splits—you pass. Optimize later.
But predict this: LLMs kill LeetCode worship. Soon, “solve 105” becomes “prompt GPT.” Interviews shift to system design. Trees? Table stakes, forgotten.
Don’t buy the hype. TraceLit visualizer? Gimmick. Step through yourself—pen, paper. Builds muscle.
Deeper dive: duplicates? Problem assumes unique vals. Real trees? Multisets. Crashes hard. Addendum: use hash of indices, but preorder pop assumes order. Messy.
Improved version—because I’m not lazy:
Precompute inorder index hashmap. O(n) build. Then recurse with indices, no pops/slices. Slices copy—extra O(n²) space hidden. Indices only: pure O(n).
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder: return None
idx_map = {val: i for i, val in enumerate(inorder)}
def helper(pre_start, pre_end, in_start, in_end):
if pre_start > pre_end: return None
root_val = preorder[pre_start]
root = TreeNode(root_val)
root_idx = idx_map[root_val]
left_size = root_idx - in_start
root.left = helper(pre_start+1, pre_start+left_size, in_start, root_idx-1)
root.right = helper(pre_start+left_size+1, pre_end, root_idx+1, in_end)
return root
return helper(0, len(preorder)-1, 0, len(inorder)-1)
See? No mutations. No scans. O(n) time, O(n) space. LeetCode accepts both. Pick your poison.
Critique their PR spin: “Step-by-step visual trace.” Yawn. Everyone’s seen it. Medium tags—Binary Tree | Recursion | Array | Tree Construction—like SEO vomit.
Why Does LeetCode 105 Matter for Coders?
Tests tree intuition. Pre/inorder complementarity. Few problems pack recursion + arrays + trees so tight.
Master it, unlock 106 (in/post), 114 (flatten). Pattern city.
But call out the corporate game: LeetCode grinds souls for Big Tech. 105? Mid-tier medium. Prep it, sure. Obsess? Waste.
Real world: rarely raw traversals. Deserializers handle it. Know the math—good. Implement daily? Nah.
Wander a bit: remember AVL self-balancing? This assumes complete trees. Skewed inputs? Stack overflow risk, deep recursion.
Python’s fine—sys.setrecursionlimit. Prod? Iterative stack. Overkill here.
🧬 Related Insights
- Read more: Nusku: Finally, a Linux Profiler That Doesn’t Require a CS PhD
- Read more: Data-Rich Jobs Are AI’s First Casualties — Coders, Not Drivers
Frequently Asked Questions
How does LeetCode 105 reconstruct the tree?
Preorder picks root. Inorder splits subtrees. Recurse till done.
What’s wrong with LeetCode 105’s default solution?
O(n²) from repeated index searches. Use hashmap for O(n).
Does LeetCode 105 handle duplicates?
No. Assumes unique values. Real fix: indices only.
