Pattern 10 of 22

Tree Traversal Pattern: Template + 225 LeetCode Problems

Choose the order — preorder, inorder, postorder, level — and the problem solves itself.

Easy: 41
Medium: 142
Hard: 42
Time: O(n)

What the tree traversal pattern is

Almost every binary tree problem is a traversal with a small amount of work attached, so the real decision is when the node gets processed relative to its children. Preorder handles a node before descending and is what you want for copying, serialising, or passing information down from the root. Postorder handles it after both children return and is what you want whenever the answer at a node is computed from its subtrees — heights, diameters, subtree sums, the maximum path sum. Inorder is the special one: on a binary search tree it emits the values in sorted order, which turns validation, the kth smallest, and finding the minimum gap into a single scan with a pointer to the previously visited value. Level order is breadth-first search on a tree, done by draining the queue one full level at a time so each level can be handled as a unit. The iterative inorder is the traversal worth being able to write from memory, because it is the one an interviewer will ask for when recursion is ruled out.

When to use it

A value at each node depends on its subtrees — that is postorder.
The tree is a BST and the question is about sorted order, a kth element, or a range.
The answer is per level, or is the shallowest node satisfying a condition.
You are asked to serialise, clone, or rebuild a tree from traversal output.

The tree traversal template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 225 problems listed below.

PythonTree Traversal template

def inorder(root):
    result, stack, node = [], [], root

    while node or stack:
        while node:                  # descend as far left as possible
            stack.append(node)
            node = node.left

        node = stack.pop()
        result.append(node.val)      # left subtree finished, so visit now
        node = node.right            # then do the same for the right subtree

    return result

Complexity characteristics

Time: O(n)
Auxiliary space: O(h)where h is the height of the tree

Every node is visited exactly once whatever the order, so the time is linear in the node count. The space is the recursion stack or the explicit stack, which is the height of the tree: O(log n) on a balanced tree and O(n) on a degenerate one, and the degenerate one is what a test harness will hand you. Level-order traversal swaps the stack for a queue holding the widest level, which is up to n/2 nodes on a full tree.

Eyes only

Meet the tree traversal problem you did not practise.

In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.

Get Stealth Interview See pricing

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

Technical interview · 45 minsolution.pyShared editor · Python 3Longest substring without repeatsMediumGiven a string s, return the length of the longest contiguous substring in which every character is unique.s = "abcabcbb"
→ 31def length_of_longest_substring(s: str) -> int:2 last_seen = {}3 left = best = 04 for right, ch in enumerate(s):5 if ch in last_seen and last_seen[ch] >= left:

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 Terra

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

Primary display

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

All 225 tree traversal LeetCode problems

Every problem in the library the tree traversal pattern applies to, grouped by LeetCode's own difficulty rating. 167 of the 225 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Easy (41)

Easy problems
No.	Problem	Topics
0094	Binary Tree Inorder Traversal	Stack, Tree, Depth-First Search +1
0100	Same Tree	Tree, Depth-First Search, Breadth-First Search +1
0101	Symmetric Tree	Tree, Depth-First Search, Breadth-First Search +1
0104	Maximum Depth of Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0108	Convert Sorted Array to Binary Search Tree	Tree, Binary Search Tree, Array +2
0110	Balanced Binary Tree	Tree, Depth-First Search, Binary Tree
0111	Minimum Depth of Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0112	Path Sum	Tree, Depth-First Search, Breadth-First Search +1
0144	Binary Tree Preorder Traversal	Stack, Tree, Depth-First Search +1
0145	Binary Tree Postorder Traversal	Stack, Tree, Depth-First Search +1
0222	Count Complete Tree Nodes	Bit Manipulation, Tree, Binary Search +1
0226	Invert Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0257	Binary Tree Paths	Tree, Depth-First Search, String +2
0404	Sum of Left Leaves	Tree, Depth-First Search, Breadth-First Search +1
0501	Find Mode in Binary Search Tree	Tree, Depth-First Search, Binary Search Tree +1
0530	Minimum Absolute Difference in BST	Tree, Depth-First Search, Breadth-First Search +2
0543	Diameter of Binary Tree	Tree, Depth-First Search, Binary Tree
0559	Maximum Depth of N-ary Tree	Tree, Depth-First Search, Breadth-First Search
0563	Binary Tree Tilt	Tree, Depth-First Search, Binary Tree
0572	Subtree of Another Tree	Tree, Depth-First Search, Binary Tree +2
0589	N-ary Tree Preorder Traversal	Stack, Tree, Depth-First Search
0590	N-ary Tree Postorder Traversal	Stack, Tree, Depth-First Search
0617	Merge Two Binary Trees	Tree, Depth-First Search, Breadth-First Search +1
0637	Average of Levels in Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0653	Two Sum IV - Input is a BST	Tree, Depth-First Search, Breadth-First Search +4
0671	Second Minimum Node In a Binary Tree	Tree, Depth-First Search, Binary Tree
0700	Search in a Binary Search Tree	Tree, Binary Search Tree, Binary Tree
0703	Kth Largest Element in a Stream	Tree, Design, Binary Search Tree +3
0872	Leaf-Similar Trees	Tree, Depth-First Search, Binary Tree
0270	Closest Binary Search Tree ValuePremium	Tree, Depth-First Search, Binary Search Tree +2
0783	Minimum Distance Between BST Nodes	Tree, Depth-First Search, Breadth-First Search +2
0897	Increasing Order Search Tree	Stack, Tree, Depth-First Search +2
0938	Range Sum of BST	Tree, Depth-First Search, Binary Search Tree +1
0965	Univalued Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0993	Cousins in Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
1022	Sum of Root To Leaf Binary Numbers	Tree, Depth-First Search, Binary Tree
1379	Find a Corresponding Node of a Binary Tree in a Clone of That Tree	Tree, Depth-First Search, Breadth-First Search +1
1469	Find All The Lonely NodesPremium	Tree, Depth-First Search, Breadth-First Search +1
2236	Root Equals Sum of Children	Tree, Binary Tree
2331	Evaluate Boolean Binary Tree	Tree, Depth-First Search, Binary Tree
2689	Extract Kth Character From The Rope TreePremium	Tree, Depth-First Search, Binary Tree

Medium (142)

Medium problems
No.	Problem	Topics
0095	Unique Binary Search Trees II	Tree, Binary Search Tree, Dynamic Programming +2
0096	Unique Binary Search Trees	Tree, Binary Search Tree, Math +2
0098	Validate Binary Search Tree	Tree, Depth-First Search, Binary Search Tree +1
0099	Recover Binary Search Tree	Tree, Depth-First Search, Binary Search Tree +1
0102	Binary Tree Level Order Traversal	Tree, Breadth-First Search, Binary Tree
0103	Binary Tree Zigzag Level Order Traversal	Tree, Breadth-First Search, Binary Tree
0105	Construct Binary Tree from Preorder and Inorder Traversal	Tree, Array, Hash Table +2
0106	Construct Binary Tree from Inorder and Postorder Traversal	Tree, Array, Hash Table +2
0107	Binary Tree Level Order Traversal II	Tree, Breadth-First Search, Binary Tree
0109	Convert Sorted List to Binary Search Tree	Tree, Binary Search Tree, Linked List +2
0113	Path Sum II	Tree, Depth-First Search, Backtracking +1
0114	Flatten Binary Tree to Linked List	Stack, Tree, Depth-First Search +2
0116	Populating Next Right Pointers in Each Node	Tree, Depth-First Search, Breadth-First Search +2
0117	Populating Next Right Pointers in Each Node II	Tree, Depth-First Search, Breadth-First Search +2
0129	Sum Root to Leaf Numbers	Tree, Depth-First Search, Binary Tree
0173	Binary Search Tree Iterator	Stack, Tree, Design +3
0199	Binary Tree Right Side View	Tree, Depth-First Search, Breadth-First Search +1
0230	Kth Smallest Element in a BST	Tree, Depth-First Search, Binary Search Tree +1
0235	Lowest Common Ancestor of a Binary Search Tree	Tree, Depth-First Search, Binary Search Tree +1
0236	Lowest Common Ancestor of a Binary Tree	Tree, Depth-First Search, Binary Tree
0331	Verify Preorder Serialization of a Binary Tree	Stack, Tree, String +1
0337	House Robber III	Tree, Depth-First Search, Dynamic Programming +1
0341	Flatten Nested List Iterator	Stack, Tree, Depth-First Search +3
0427	Construct Quad Tree	Tree, Array, Divide and Conquer +1
0429	N-ary Tree Level Order Traversal	Tree, Breadth-First Search
0437	Path Sum III	Tree, Depth-First Search, Binary Tree
0449	Serialize and Deserialize BST	Tree, Depth-First Search, Breadth-First Search +4
0450	Delete Node in a BST	Tree, Binary Search Tree, Binary Tree
0508	Most Frequent Subtree Sum	Tree, Depth-First Search, Hash Table +1
0513	Find Bottom Left Tree Value	Tree, Depth-First Search, Breadth-First Search +1
0515	Find Largest Value in Each Tree Row	Tree, Depth-First Search, Breadth-First Search +1
0538	Convert BST to Greater Tree	Tree, Depth-First Search, Binary Search Tree +1
0558	Logical OR of Two Binary Grids Represented as Quad-Trees	Tree, Divide and Conquer
0606	Construct String from Binary Tree	Tree, Depth-First Search, String +1
0623	Add One Row to Tree	Tree, Depth-First Search, Breadth-First Search +1
0652	Find Duplicate Subtrees	Tree, Depth-First Search, Hash Table +1
0654	Maximum Binary Tree	Stack, Tree, Array +3
0655	Print Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0662	Maximum Width of Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0669	Trim a Binary Search Tree	Tree, Depth-First Search, Binary Search Tree +1
0687	Longest Univalue Path	Tree, Depth-First Search, Binary Tree
0690	Employee Importance	Tree, Depth-First Search, Breadth-First Search +2
0701	Insert into a Binary Search Tree	Tree, Binary Search Tree, Binary Tree
1161	Maximum Level Sum of a Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
1372	Longest ZigZag Path in a Binary Tree	Tree, Depth-First Search, Dynamic Programming +1
1448	Count Good Nodes in Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0156	Binary Tree Upside DownPremium	Tree, Depth-First Search, Binary Tree
0250	Count Univalue SubtreesPremium	Tree, Depth-First Search, Binary Tree
0255	Verify Preorder Sequence in Binary Search TreePremium	Stack, Tree, Binary Search Tree +4
0285	Inorder Successor in BSTPremium	Tree, Depth-First Search, Binary Search Tree +1
0298	Binary Tree Longest Consecutive SequencePremium	Tree, Depth-First Search, Binary Tree
0314	Binary Tree Vertical Order TraversalPremium	Tree, Depth-First Search, Breadth-First Search +3
0333	Largest BST SubtreePremium	Tree, Depth-First Search, Binary Search Tree +2
0366	Find Leaves of Binary TreePremium	Tree, Depth-First Search, Binary Tree
0426	Convert Binary Search Tree to Sorted Doubly Linked ListPremium	Stack, Tree, Depth-First Search +4
0510	Inorder Successor in BST IIPremium	Tree, Binary Search Tree, Binary Tree
0536	Construct Binary Tree from StringPremium	Stack, Tree, Depth-First Search +2
0545	Boundary of Binary TreePremium	Tree, Depth-First Search, Binary Tree
0549	Binary Tree Longest Consecutive Sequence IIPremium	Tree, Depth-First Search, Binary Tree
0582	Kill ProcessPremium	Tree, Depth-First Search, Breadth-First Search +2
0663	Equal Tree PartitionPremium	Tree, Depth-First Search, Binary Tree
0666	Path Sum IVPremium	Tree, Depth-First Search, Array +2
0742	Closest Leaf in a Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
0776	Split BSTPremium	Tree, Binary Search Tree, Recursion +1
0814	Binary Tree Pruning	Tree, Depth-First Search, Binary Tree
0863	All Nodes Distance K in Binary Tree	Tree, Depth-First Search, Breadth-First Search +2
0865	Smallest Subtree with all the Deepest Nodes	Tree, Depth-First Search, Breadth-First Search +2
0889	Construct Binary Tree from Preorder and Postorder Traversal	Tree, Array, Hash Table +2
0894	All Possible Full Binary Trees	Tree, Recursion, Memoization +2
0919	Complete Binary Tree Inserter	Tree, Breadth-First Search, Design +1
0951	Flip Equivalent Binary Trees	Tree, Depth-First Search, Binary Tree
0958	Check Completeness of a Binary Tree	Tree, Breadth-First Search, Binary Tree
0971	Flip Binary Tree To Match Preorder Traversal	Tree, Depth-First Search, Binary Tree
0979	Distribute Coins in Binary Tree	Tree, Depth-First Search, Binary Tree
0988	Smallest String Starting From Leaf	Tree, Depth-First Search, String +2
0998	Maximum Binary Tree II	Tree, Binary Tree
1008	Construct Binary Search Tree from Preorder Traversal	Stack, Tree, Binary Search Tree +3
1026	Maximum Difference Between Node and Ancestor	Tree, Depth-First Search, Binary Tree
1038	Binary Search Tree to Greater Sum Tree	Tree, Depth-First Search, Binary Search Tree +1
1080	Insufficient Nodes in Root to Leaf Paths	Tree, Depth-First Search, Binary Tree
1104	Path In Zigzag Labelled Binary Tree	Tree, Math, Binary Tree
1110	Delete Nodes And Return Forest	Tree, Depth-First Search, Array +2
1120	Maximum Average SubtreePremium	Tree, Depth-First Search, Binary Tree
1123	Lowest Common Ancestor of Deepest Leaves	Tree, Depth-First Search, Breadth-First Search +2
1145	Binary Tree Coloring Game	Tree, Depth-First Search, Binary Tree
1214	Two Sum BSTsPremium	Stack, Tree, Depth-First Search +4
1245	Tree DiameterPremium	Tree, Depth-First Search, Breadth-First Search +2
1257	Smallest Common RegionPremium	Tree, Depth-First Search, Breadth-First Search +3
1261	Find Elements in a Contaminated Binary Tree	Tree, Depth-First Search, Breadth-First Search +3
1273	Delete Tree NodesPremium	Tree, Depth-First Search, Breadth-First Search +1
1302	Deepest Leaves Sum	Tree, Depth-First Search, Breadth-First Search +1
1305	All Elements in Two Binary Search Trees	Tree, Depth-First Search, Binary Search Tree +2
1315	Sum of Nodes with Even-Valued Grandparent	Tree, Depth-First Search, Breadth-First Search +1
1325	Delete Leaves With a Given Value	Tree, Depth-First Search, Binary Tree
1339	Maximum Product of Splitted Binary Tree	Tree, Depth-First Search, Binary Tree
1361	Validate Binary Tree Nodes	Tree, Depth-First Search, Breadth-First Search +3
1367	Linked List in Binary Tree	Tree, Depth-First Search, Linked List +1
1376	Time Needed to Inform All Employees	Tree, Depth-First Search, Breadth-First Search
1382	Balance a Binary Search Tree	Greedy, Tree, Depth-First Search +3
1430	Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
1443	Minimum Time to Collect All Apples in a Tree	Tree, Depth-First Search, Breadth-First Search +1
1457	Pseudo-Palindromic Paths in a Binary Tree	Bit Manipulation, Tree, Depth-First Search +2
1485	Clone Binary Tree With Random PointerPremium	Tree, Depth-First Search, Breadth-First Search +2
1490	Clone N-ary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
1506	Find Root of N-Ary TreePremium	Bit Manipulation, Tree, Depth-First Search +1
1519	Number of Nodes in the Sub-Tree With the Same Label	Tree, Depth-First Search, Breadth-First Search +2
1522	Diameter of N-Ary TreePremium	Tree, Depth-First Search
1530	Number of Good Leaf Nodes Pairs	Tree, Depth-First Search, Binary Tree
1586	Binary Search Tree Iterator IIPremium	Stack, Tree, Design +3
1600	Throne Inheritance	Tree, Depth-First Search, Design +1
1602	Find Nearest Right Node in Binary TreePremium	Tree, Breadth-First Search, Binary Tree
1609	Even Odd Tree	Tree, Breadth-First Search, Binary Tree
1612	Check If Two Expression Trees are EquivalentPremium	Tree, Depth-First Search, Hash Table +2
1628	Design an Expression Tree With Evaluate FunctionPremium	Stack, Tree, Design +3
1644	Lowest Common Ancestor of a Binary Tree IIPremium	Tree, Depth-First Search, Binary Tree
1650	Lowest Common Ancestor of a Binary Tree IIIPremium	Tree, Hash Table, Two Pointers +1
1660	Correct a Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +2
1666	Change the Root of a Binary TreePremium	Tree, Depth-First Search, Binary Tree
1676	Lowest Common Ancestor of a Binary Tree IVPremium	Tree, Depth-First Search, Hash Table +1
1740	Find Distance in a Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +2
1902	Depth of BST Given Insertion OrderPremium	Tree, Binary Search Tree, Array +2
1973	Count Nodes Equal to Sum of DescendantsPremium	Tree, Depth-First Search, Binary Tree
1993	Operations on Tree	Tree, Depth-First Search, Breadth-First Search +3
2049	Count Nodes With the Highest Score	Tree, Depth-First Search, Array +1
2096	Step-By-Step Directions From a Binary Tree Node to Another	Tree, Depth-First Search, String +1
2196	Create Binary Tree From Descriptions	Tree, Array, Hash Table +1
2265	Count Nodes Equal to Average of Subtree	Tree, Depth-First Search, Binary Tree
2368	Reachable Nodes With Restrictions	Tree, Depth-First Search, Breadth-First Search +4
2378	Choose Edges to Maximize Score in a TreePremium	Tree, Depth-First Search, Dynamic Programming
2385	Amount of Time for Binary Tree to Be Infected	Tree, Depth-First Search, Breadth-First Search +2
2415	Reverse Odd Levels of Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
2445	Number of Nodes With Value OnePremium	Tree, Depth-First Search, Breadth-First Search +2
2467	Most Profitable Path in a Tree	Tree, Depth-First Search, Breadth-First Search +2
2471	Minimum Number of Operations to Sort a Binary Tree by Level	Tree, Breadth-First Search, Binary Tree
2476	Closest Nodes Queries in a Binary Search Tree	Tree, Depth-First Search, Binary Search Tree +3
2477	Minimum Fuel Cost to Report to the Capital	Tree, Depth-First Search, Breadth-First Search +1
2583	Kth Largest Sum in a Binary Tree	Tree, Breadth-First Search, Binary Tree +1
2641	Cousins in Binary Tree II	Tree, Depth-First Search, Breadth-First Search +2
2673	Make Costs of Paths Equal in a Binary Tree	Greedy, Tree, Array +2
2764	Is Array a Preorder of Some ‌Binary TreePremium	Stack, Tree, Depth-First Search +1
2773	Height of Special Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
2925	Maximum Score After Applying Operations on a Tree	Tree, Depth-First Search, Dynamic Programming

Hard (42)

Hard problems
No.	Problem	Topics
0124	Binary Tree Maximum Path Sum	Tree, Depth-First Search, Dynamic Programming +1
0297	Serialize and Deserialize Binary Tree	Tree, Depth-First Search, Breadth-First Search +3
0272	Closest Binary Search Tree Value IIPremium	Stack, Tree, Depth-First Search +4
0428	Serialize and Deserialize N-ary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
0431	Encode N-ary Tree to Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +2
0834	Sum of Distances in Tree	Tree, Depth-First Search, Graph +1
0968	Binary Tree Cameras	Tree, Depth-First Search, Dynamic Programming +1
0987	Vertical Order Traversal of a Binary Tree	Tree, Depth-First Search, Breadth-First Search +3
1028	Recover a Tree From Preorder Traversal	Tree, Depth-First Search, String +1
1373	Maximum Sum BST in Binary Tree	Tree, Depth-First Search, Binary Search Tree +2
1377	Frog Position After T Seconds	Tree, Depth-First Search, Breadth-First Search +1
1483	Kth Ancestor of a Tree Node	Bit Manipulation, Tree, Depth-First Search +4
1516	Move Sub-Tree of N-Ary TreePremium	Tree, Depth-First Search
1569	Number of Ways to Reorder Array to Get Same BST	Tree, Union Find, Binary Search Tree +7
1597	Build Binary Expression Tree From Infix ExpressionPremium	Stack, Tree, String +1
1617	Count Subtrees With Max Distance Between Cities	Bit Manipulation, Tree, Dynamic Programming +2
1719	Number Of Ways To Reconstruct A Tree	Tree, Graph
1766	Tree of Coprimes	Tree, Depth-First Search, Array +2
1916	Count Ways to Build Rooms in an Ant Colony	Tree, Graph, Topological Sort +3
1932	Merge BSTs to Create Single BST	Tree, Depth-First Search, Hash Table +2
2003	Smallest Missing Genetic Value in Each Subtree	Tree, Depth-First Search, Union Find +1
2005	Subtree Removal Game with Fibonacci TreePremium	Tree, Math, Dynamic Programming +2
2246	Longest Path With Different Adjacent Characters	Tree, Depth-First Search, Graph +3
2277	Closest Node to Path in TreePremium	Tree, Depth-First Search, Breadth-First Search +1
2313	Minimum Flips in Binary Tree to Get ResultPremium	Tree, Depth-First Search, Dynamic Programming +1
2322	Minimum Score After Removals on a Tree	Bit Manipulation, Tree, Depth-First Search +1
2421	Number of Good Paths	Tree, Union Find, Graph +3
2440	Create Components With Same Value	Tree, Depth-First Search, Array +2
2458	Height of Binary Tree After Subtree Removal Queries	Tree, Depth-First Search, Breadth-First Search +2
2479	Maximum XOR of Two Non-Overlapping SubtreesPremium	Tree, Depth-First Search, Graph +1
2509	Cycle Length Queries in a Tree	Tree, Array, Binary Tree
2538	Difference Between Maximum and Minimum Price Sum	Tree, Depth-First Search, Array +1
2581	Count Number of Possible Root Nodes	Tree, Depth-First Search, Array +2
2603	Collect Coins in a Tree	Tree, Graph, Topological Sort +1
2646	Minimize the Total Price of the Trips	Tree, Depth-First Search, Graph +2
2791	Count Paths That Can Form a Palindrome in a Tree	Bit Manipulation, Tree, Depth-First Search +2
2792	Count Nodes That Are Great EnoughPremium	Tree, Depth-First Search, Divide and Conquer +1
2846	Minimum Edge Weight Equilibrium Queries in a Tree	Tree, Graph, Array +1
2867	Count Valid Paths in a Tree	Tree, Depth-First Search, Math +2
2872	Maximum Number of K-Divisible Components	Tree, Depth-First Search
2920	Maximum Points After Collecting Coins From All Nodes	Bit Manipulation, Tree, Depth-First Search +3
2973	Find Number of Coins to Place in Tree Nodes	Tree, Depth-First Search, Dynamic Programming +2

Tree Traversal pattern FAQ

What is the tree traversal pattern?

Almost every binary tree problem is a traversal with a small amount of work attached, so the real decision is when the node gets processed relative to its children.

How many LeetCode problems use the tree traversal pattern?

This page lists 225 LeetCode problems that the tree traversal pattern applies to: 41 Easy, 142 Medium and 42 Hard. 167 of them carry a complete Python solution with complexity analysis.

What is the time complexity of the tree traversal pattern?

O(n) time and O(h), where h is the height of the tree space. Every node is visited exactly once whatever the order, so the time is linear in the node count. The space is the recursion stack or the explicit stack, which is the height of the tree: O(log n) on a balanced tree and O(n) on a degenerate one, and the degenerate one is what a test harness will hand you. Level-order traversal swaps the stack for a queue holding the widest level, which is up to n/2 nodes on a full tree.

When should I use the tree traversal pattern in an interview?

A value at each node depends on its subtrees — that is postorder. The tree is a BST and the question is about sorted order, a kth element, or a range.

Which tree traversal problem should I start with?

LeetCode 94. Binary Tree Inorder Traversal is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.

What patterns are related to tree traversal?

Depth-First Search, Breadth-First Search, Backtracking, Trie. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.

More ways in: all 22 patterns, the curated study lists, or the full problem list.

What the tree traversal pattern is

When to use it

The tree traversal template in Python

Complexity characteristics

Meet the tree traversal problem you did not practise.

Approach

Approach

Approach

All 225 tree traversal LeetCode problems

Easy (41)41

Medium (142)142

Hard (42)42

Related patterns

Tree Traversal pattern FAQ

What is the tree traversal pattern?

How many LeetCode problems use the tree traversal pattern?

What is the time complexity of the tree traversal pattern?

When should I use the tree traversal pattern in an interview?

Which tree traversal problem should I start with?

What patterns are related to tree traversal?

Easy (41)

Medium (142)

Hard (42)