After arrays and strings, trees and linked lists are the most tested topics in SDE1 and entry-level FAANG coding rounds. Amazon explicitly asks about binary trees and BSTs in a large proportion of its SDE1 interview rounds. Google L3 loops regularly include tree traversal and path problems. Stack-based questions appear across all companies, often disguised as real-world scenarios.
This blog covers the most frequently reported problems from these three categories, with verified, clean solutions, full complexity analysis, and the reasoning you need to narrate in a live interview.
All solutions are in Python and have been verified for correctness.
What to Expect in SDE1 Loops for These Topics
Trees: Binary tree traversals (inorder, preorder, postorder, level-order) are baseline expectations. Interviewers often start with a traversal and follow up with a harder tree problem. Amazon specifically tests LCA (Lowest Common Ancestor) and BST validation frequently.
Linked Lists: Reversal, cycle detection, and merge operations are the most common. These test pointer manipulation under time pressure, the logic is straightforward but easy to get wrong under stress.
Stacks: Often appear disguised as bracket matching, expression evaluation, or "next greater element" problems. The monotonic stack pattern appears at Medium difficulty across all companies.
Part 1: Binary Trees
The TreeNode Class (used in all tree problems below)
python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
Problem 1: Inorder Traversal of a Binary Tree
Difficulty: Easy. Asked at: Amazon, Google, Meta, baseline tree question, frequently used as a warm-up. LeetCode: #94
Problem Statement
Given the root of a binary tree, return the inorder traversal of its node values (left → root → right).
Example:
Input tree:
1
\
2
/
3
Output: [1, 3, 2]
Approach
Inorder traversal visits the left subtree, then the root, then the right subtree. Both recursive and iterative approaches are valid, interviewers at Google often ask for the iterative version as a follow-up.
Recursive Solution
python
def inorder_traversal(root):
result = []
def dfs(node):
if not node:
return
dfs(node.left)
result.append(node.val)
dfs(node.right)
dfs(root)
return result
Iterative Solution (common follow-up)
python
def inorder_traversal_iterative(root):
result = []
stack = []
current = root
while current or stack:
# Go as far left as possible
while current:
stack.append(current)
current = current.left
# Process the node
current = stack.pop()
result.append(current.val)
# Move to the right subtree
current = current.right
return result
Complexity
- Time: O(n) - every node is visited exactly once
- Space: O(h)- where h is the height of the tree (O(log n) for balanced, O(n) worst case for skewed tree)
Problem 2: Maximum Depth of a Binary Tree
Difficulty: Easy. Asked at: Amazon, Google, very high frequency at entry level. LeetCode: #104
Problem Statement
Given the root of a binary tree, return its maximum depth, the number of nodes along the longest path from the root to the farthest leaf.
Example:
Input tree:
3
/ \
9 20
/ \
15 7
Output: 3
Approach
The maximum depth of a tree is 1 + the maximum of the depths of its left and right subtrees. This is naturally recursive. The base case: a null node has depth 0.
Solution
python
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
Trace Through the Example
max_depth(3):
left = max_depth(9) → max_depth(None) + max_depth(None) → 1 + max(0,0) = 1
right = max_depth(20) → max_depth(15) and max_depth(7) are both leaves → 1 each
→ 1 + max(1, 1) = 2
return 1 + max(1, 2) = 3 ✓
Complexity
- Time: O(n) - every node visited once
- Space: O(h) - recursion stack depth equals tree height
Problem 3: Level Order Traversal (BFS)
Difficulty: Medium. Asked at: Amazon, Google, Meta, high frequency; tests whether candidates know BFS on trees. LeetCode: #102
Problem Statement
Given the root of a binary tree, return the level-order traversal of its node values, left to right, level by level, as a list of lists.
Example:
Input tree:
3
/ \
9 20
/ \
15 7
Output: [[3], [9, 20], [15, 7]]
Approach
Use a queue (BFS). At each step, process all nodes at the current level before moving to the next. Track level boundaries by recording the queue size at the start of each level.
Solution
python
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
Trace Through the Example
Start: queue = [3]
Level 1: size=1. Process 3 → current_level=[3]. Add 9, 20. queue=[9,20]
Level 2: size=2. Process 9 → current_level=[9]. No children.
Process 20 → current_level=[9,20]. Add 15, 7. queue=[15,7]
Level 3: size=2. Process 15 → current_level=[15]. No children.
Process 7 → current_level=[15,7]. No children.
Output: [[3],[9,20],[15,7]] ✓
Complexity
- Time: O(n) - every node processed exactly once
- Space: O(w) - where w is the maximum width of the tree (at most n/2 for the last level)
Problem 4: Validate Binary Search Tree
Difficulty: Medium. Asked at: Amazon, very high frequency; specifically reported across multiple SDE1 Amazon loops. LeetCode: #98
Problem Statement
Given the root of a binary tree, determine if it is a valid Binary Search Tree (BST). A valid BST satisfies: the left subtree contains only nodes with values less than the node's value, and the right subtree contains only nodes with values greater than the node's value. Both subtrees must also be valid BSTs.
Example:
Input:
2
/ \
1 3
Output: True
Input:
5
/ \
1 4
/ \
3 6
Output: False (4 is in right subtree of 5 but 4 < 5)
Approach
A common mistake is checking only that each node's left child is smaller and right child is larger. This misses cases where a node violates the BST property with an ancestor.
The correct approach: pass valid bounds (min_val, max_val) down the tree. Every node must satisfy min_val < node.val < max_val. Initially bounds are (-∞, +∞). Going left tightens the upper bound; going right tightens the lower bound.
Solution
python
def is_valid_bst(root):
def validate(node, min_val, max_val):
if not node:
return True
if node.val <= min_val or node.val >= max_val:
return False
return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf'))
Trace Through the Invalid Example
Tree:
5
/ \
1 4
/ \
3 6
validate(5, -inf, inf): 5 in range ✓
validate(1, -inf, 5): 1 in range ✓ → True
validate(4, 5, inf): 4 <= 5 → False ✗
Output: False ✓
Complexity
- Time: O(n) - every node visited once
- Space: O(h)- recursion stack
Part 2: Linked Lists
The ListNode Class (used in all linked list problems below)
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
Problem 5: Reverse a Linked List
Difficulty: Easy. Asked at: Amazon, Google, Meta, Apple, one of the most frequently asked linked list questions at all levels; SDE1 baseline. LeetCode: #206
Problem Statement
Given the head of a singly linked list, reverse the list and return the new head.
Example:
Input: 1 → 2 → 3 → 4 → 5 → None
Output: 5 → 4 → 3 → 2 → 1 → None
Approach
Use three pointers: prev (starts as None), current (starts at head), and next_node (temporary storage). At each step, save current.next, point current.next to prev, then advance both prev and current forward.
Iterative Solution
python
def reverse_list(head):
prev = None
current = head
while current:
next_node = current.next # save next
current.next = prev # reverse the link
prev = current # move prev forward
current = next_node # move current forward
return prev # prev is the new head
Trace Through the Example
Initial: prev=None, current=1→2→3→4→5
Step 1: next=2→3→4→5, 1.next=None, prev=1, current=2
Step 2: next=3→4→5, 2.next=1, prev=2, current=3
Step 3: next=4→5, 3.next=2, prev=3, current=4
Step 4: next=5, 4.next=3, prev=4, current=5
Step 5: next=None, 5.next=4, prev=5, current=None
Return prev = 5→4→3→2→1→None ✓
Complexity
- Time: O(n)
- Space: O(1) - in-place, no extra data structures
Recursive Solution (common follow-up)
python
def reverse_list_recursive(head):
if not head or not head.next:
return head
new_head = reverse_list_recursive(head.next)
head.next.next = head
head.next = None
return new_head
- Time: O(n)
- Space: O(n) — recursion stack
Problem 6: Detect Cycle in a Linked List
Difficulty: Easy. Asked at: Amazon, Google, frequently asked; tests knowledge of Floyd's algorithm. LeetCode: #141
Problem Statement
Given the head of a linked list, determine if it contains a cycle. A cycle exists if some node can be reached again by following next pointers.
Example:
Input: 3 → 2 → 0 → -4 → (back to node with val 2)
Output: True
Approach
Use Floyd's Cycle Detection algorithm (fast and slow pointers). slow moves one step at a time, fast moves two steps. If there is a cycle, they will eventually meet. If fast reaches None, there is no cycle.
Solution
python
def has_cycle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Why This Works
In a cyclic list, the fast pointer gains one step on the slow pointer per iteration (since fast moves 2 and slow moves 1). Eventually, fast laps slow inside the cycle and they meet. In a non-cyclic list, fast reaches None first.
Complexity
- Time: O(n)
- Space: O(1) - -only two pointers, no extra storage
Problem 7: Merge Two Sorted Linked Lists
Difficulty: Easy. Asked at: Amazon, Google, Meta, very high frequency across all FAANG SDE1 loops. LeetCode: #21
Problem Statement
Given the heads of two sorted linked lists, merge them into one sorted linked list and return its head.
Example:
Input: list1 = 1 → 2 → 4, list2 = 1 → 3 → 4
Output: 1 → 1 → 2 → 3 → 4 → 4
Approach
Use a dummy node to simplify edge cases. Maintain a current pointer. At each step, compare the heads of both lists and append the smaller one to current, advancing that list's pointer. Once one list is exhausted, append the remaining nodes of the other.
Solution
python
def merge_two_lists(list1, list2):
dummy = ListNode(0)
current = dummy
while list1 and list2:
if list1.val <= list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
# Attach remaining nodes
current.next = list1 if list1 else list2
return dummy.next
Trace Through the Example
list1 = 1→2→4, list2 = 1→3→4
Step 1: 1 <= 1 → append list1's 1. list1=2→4, current=1
Step 2: 1 <= 2 → append list2's 1. list2=3→4, current=1
Step 3: 2 <= 3 → append list1's 2. list1=4, current=2
Step 4: 3 <= 4 → append list2's 3. list2=4, current=3
Step 5: 4 <= 4 → append list1's 4. list1=None, current=4
list1 exhausted → append remaining list2 = 4
Output: 1→1→2→3→4→4 ✓
Complexity
- Time: O(n + m) - where n and m are the lengths of the two lists
- Space: O(1) - we reuse existing nodes
Part 3: Stacks
Problem 8: Valid Parentheses
Difficulty: Easy. Asked at: Amazon, Google, Meta, Apple, one of the most commonly asked stack problems at SDE1 level. LeetCode: #20
Problem Statement
Given a string containing only (, ), {, }, [, ], determine if the string is valid. A string is valid if every open bracket is closed by the correct type of bracket in the correct order.
Example:
Input: s = "()[]{}" → Output: True
Input: s = "([)]" → Output: False
Input: s = "{[]}" → Output: True
Approach
Use a stack. When we see an opening bracket, push it. When we see a closing bracket, check if the top of the stack is the matching opening bracket. If yes, pop. If no (or stack is empty), return False. At the end, the stack must be empty.
Solution
python
def is_valid(s):
stack = []
matching = {')': '(', '}': '{', ']': '['}
for char in s:
if char in matching: # closing bracket
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
else: # opening bracket
stack.append(char)
return len(stack) == 0
Trace Through "{[]}":
char='{': opening → stack=['{']
char='[': opening → stack=['{','[']
char=']': closing, matching=']'->'['. Top of stack='['. Match! Pop. stack=['{']
char='}': closing, matching='}'->'{'. Top of stack='{'. Match! Pop. stack=[]
Stack is empty → True ✓
Complexity
- Time: O(n)
- Space: O(n) - worst case all opening brackets pushed onto stack
Problem 9: Min Stack
Difficulty: Medium. Asked at: Amazon, Google, frequently asked; tests ability to design a data structure. LeetCode: #155
Problem Statement
Design a stack that supports push, pop, top, and get_min, all in O(1) time. get_min must return the minimum element in the stack at any time.
Example:
MinStack stack
stack.push(-2)
stack.push(0)
stack.push(-3)
stack.get_min() → -3
stack.pop()
stack.top() → 0
stack.get_min() → -2
Approach
The challenge is that after popping the current minimum, we need to know the previous minimum. Use two stacks: one main stack for all values, and one min stack that stores the current minimum at each state.
Whenever we push a value, also push to the min stack the new minimum (the smaller of the new value and the current top of the min stack).
Solution
python
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [] # each position holds the minimum at that point
def push(self, val):
self.stack.append(val)
if self.min_stack:
self.min_stack.append(min(val, self.min_stack[-1]))
else:
self.min_stack.append(val)
def pop(self):
self.stack.pop()
self.min_stack.pop()
def top(self):
return self.stack[-1]
def get_min(self):
return self.min_stack[-1]
Trace Through the Example
push(-2): stack=[-2], min_stack=[-2]
push(0): stack=[-2,0], min_stack=[-2,-2] (min(-2,0)=-2 is still min)
push(-3): stack=[-2,0,-3], min_stack=[-2,-2,-3]
get_min() → min_stack[-1] = -3 ✓
pop(): stack=[-2,0], min_stack=[-2,-2]
top() → stack[-1] = 0 ✓
get_min() → min_stack[-1] = -2 ✓
Complexity
- Time: O(1) for all operations
- Space: O(n) - two stacks of size n
How Trees, Linked Lists, and Stacks Connect in Real Interviews
Interviewers at Amazon and Google rarely ask these in isolation. Common combinations at SDE1 level:
- Level-order traversal → follow-up: "Now return it in zigzag order" (alternate directions per level, still BFS, but alternate append direction)
- Reverse linked list → follow-up: "Reverse only a portion of the list between positions m and n"
- Valid parentheses → follow-up: "What if we had 100 types of bracket pairs?"
Being prepared for the follow-up question is what moves you from a Hire to a Strong Hire at SDE1 level.
Practising These Under Real Interview Conditions
The problems above are straightforward on paper. Under a 30-minute timer, with an interviewer watching and asking follow-up questions, they are genuinely harder.
The pointer logic in linked list reversal is the most common source of live interview errors, candidates who solved it 20 times alone still make mistakes when they're narrating and managing time simultaneously.
At Intervue.io, SDE1 mock sessions are conducted by engineers who know exactly what Amazon, Google, Meta, and product companies look for at the entry level. You get feedback on your pointer handling, your traversal logic, your edge case awareness, and your communication, not just whether the code compiles.
👉 Book an SDE1 mock session on Intervue.io
Summary
The most frequently asked SDE1 coding problems in trees, linked lists, and stacks at FAANG and product companies:
Trees:
- Inorder Traversal: recursive and iterative
- Maximum Depth: one of the most common entry-level tree problems
- Level Order Traversal: BFS with level boundary tracking
- Validate BST: bounds-passing approach, not just parent-child comparison
Linked Lists:
- Reverse a Linked List: three-pointer iterative approach
- Detect Cycle: Floyd's fast-slow pointer algorithm
- Merge Two Sorted Lists: dummy node + pointer comparison
Stacks:
- Valid Parentheses: matching map + stack
- Min Stack: two-stack design for O(1) minimum
Understand the pattern behind each. Practice them under a timer. Narrate your approach out loud from the first day of preparation.
👉 Practice these problems in a live SDE1 mock on Intervue.io
