Tree Input Formats
The Problem Nobody Warns You About
On LeetCode, the tree is handed to you as a TreeNode* parameter. You never think about input.
In an interview, the interviewer says: "You have a tree with n nodes." That's it. No format specified. No TreeNode* magically appearing. You're expected to ask: "How is the tree given?" — and then handle whatever they say.
Knowing the algorithm is not enough. You also need to build the tree from raw input.
The Three Formats You Must Handle
Format 1: The Object Structure (LeetCode / Interview Standard)
You're handed a TreeNode* root. The struct has val, left, right.
Always establish the struct on the whiteboard immediately so you and the interviewer agree on properties:
This is the format for 90% of interview tree problems. If the interviewer doesn't specify, assume this and confirm.
Format 2: The Edge List (The "Hidden" Tree)
You're given edges like [[0,1], [0,2], [1,3]] or a list of \(n-1\) pairs.
The trap: An edge list is inherently undirected. Students often assume edges[i][0] is the parent and edges[i][1] is the child. If the interviewer passes [1,0] where 1 is the child, the code breaks.
What to do: Always build a bidirectional adjacency list and track the parent during DFS:
vector<vector<int>> adj(nodeCount + 1);
for (auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
For weighted edges, use vector<vector<pair<int,int>>> adj with {neighbor, weight}.
This is the standard format in competitive programming (Codeforces, CSES). It also appears in Google/Amazon interviews for graph-like tree problems (e.g., "find the minimum height tree").
Format 3: The Flat Array (The Implicit Tree)
You're given [5, 3, 8, 1, 4] — an array that represents a tree implicitly.
The trap: Students waste 15 minutes writing a parser to build TreeNode objects.
What to do: The children of index \(i\) are \(2i + 1\) (left) and \(2i + 2\) (right). The parent of index \(i\) is \((i - 1) / 2\). Traverse the array logically — don't build nodes.
This is the structure behind heaps and segment trees. You'll see it in problems like "check if array is a valid heap" or "find the kth smallest in a BST given as an array."
The 4 Clarification Questions
Before writing a single line, ask these. Each one changes your data structure choice:
1. "Is it a Binary Tree or a Binary Search Tree?"
The number one interview trap. If you assume BST when it's a plain binary tree, you'll write \(O(\log n)\) binary search that gives wrong answers on unsorted trees. If it IS a BST, you unlock sorted-order properties that make the problem far easier. The interviewer won't clarify unless you ask.
2. "Is it strictly a Binary Tree, or an N-Ary Tree?"
If the problem involves a company org chart, file system, or DOM tree, writing root->left immediately fails. You need vector<TreeNode*> children or an adjacency list. Ask before you define the struct.
3. "Are there Parent Pointers?"
Problems like LCA or "find path between two nodes" go from a 45-minute Hard to a 5-minute Easy if nodes have a Node* parent property. The interviewer won't volunteer this information — you must ask. If yes, you can walk up from both nodes and find the intersection.
4. "Are node values unique?"
If unique, you can use values as keys in a hash map or visited set. If duplicates exist, you must hash by node pointer or index, not by value. This silently breaks LCA code, path-finding code, and anything that stores "seen values" in a set.
Variable Naming
For tree problems, these conventions signal experience:
| Context | Use | Avoid |
|---|---|---|
| Adjacency list traversal | u (current), v (neighbor) |
x, temp, node1 |
| Object tree traversal | curr, node, root |
n, x, this |
| Recursive state passed down | depth, maxSoFar, pathSum |
d, m, s |
| Subtree results passed up | leftHeight, rightSum |
l, r, res |
In CP, single-letter variables (n, u, v) are standard. In interviews, name anything the interviewer will read on the whiteboard.
One rule: never use global variables for tree recursion state. Pass state as parameters (top-down) or return it (bottom-up). Interviewers penalize global mutable state.
The Trap: Rooted vs Unrooted
An edge list describes an unrooted tree — there's no inherent root. To root it: - Pick any node as root (usually node 0 or 1) - DFS from that node, treating the DFS parent as the tree parent
Some problems say "rooted at node 1." Others don't — you choose. For diameter or centroid, the root choice doesn't matter. For subtree queries, it does.
Try It
Exercise: Given this edge list, draw the tree rooted at node 1:
Exercise: An interviewer says "you have a binary tree, find the diameter." What do you ask before coding? (Answer: "Am I given the root node as a TreeNode*, or an edge list?")
Challenge: An interviewer says "you have a tree with weighted edges, find the farthest node from a given source." Walk through: (1) what you ask, (2) what struct you define, (3) what you build, (4) the algorithm.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| LC 297 — Serialize and Deserialize | leetcode.com/problems/serialize-and-deserialize-binary-tree | Hard |
| LC 310 — Minimum Height Trees | leetcode.com/problems/minimum-height-trees | Medium |
| CSES — Subordinates | cses.fi/problemset/task/1674 | Easy |
| LC 100 — Same Tree | leetcode.com/problems/same-tree | Easy |
| LC 101 — Symmetric Tree | leetcode.com/problems/symmetric-tree | Easy |
| LC 111 — Minimum Depth | leetcode.com/problems/minimum-depth-of-binary-tree | Easy |
What's Next?
You now know how to read, build, and convert between tree formats — and what to ask before writing code. Chapter 2 teaches you every way to traverse the tree once it's built.