Is Array a Preorder of Some Binary Tree — LeetCode 2764 Python Solution
MediumLeetCode PremiumStackTreeDepth-First SearchBinary Tree
- Problem
- #2764
- Pattern
- Stack
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Given a 0-indexed integer 2D array nodes, your task is to determine if the given array represents the preorder traversal of some binary tree. For each index i, nodes[i] = [id, parentId], where id is the id of the node at the index i and parentId is the id of its parent in the tree (if the node has no parent, then parentId == -1).
Example
- Input
- nodes = [[0,-1],[1,0],[2,0],[3,2],[4,2]]
- Output
- true
- Explanation
- The given nodes make the tree in the picture below.
Python solution
Python
class Solution:
def isPreorder(self, nodes: List[List[int]]) -> bool:
def dfs(i: int) -> int:
nonlocal k
if i != nodes[k][0]:
return False
k += 1
return all(dfs(j) for j in g[i])
g = defaultdict(list)
for i, p in nodes:
g[p].append(i)
k = 0
return dfs(nodes[0][0]) and k == len(nodes)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 2764. Is Array a Preorder of Some Binary Tree is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2764. Is Array a Preorder of Some Binary Tree?
- LeetCode 2764. Is Array a Preorder of Some Binary Tree is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2764. Is Array a Preorder of Some Binary Tree?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2764. Is Array a Preorder of Some Binary Tree?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2764. Is Array a Preorder of Some Binary Tree cover?
- LeetCode 2764. Is Array a Preorder of Some Binary Tree is tagged Stack, Tree, Depth-First Search and Binary Tree on LeetCode.
- Is LeetCode 2764. Is Array a Preorder of Some Binary Tree a premium problem?
- Yes. LeetCode 2764. Is Array a Preorder of Some Binary Tree is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.