Find Mode in Binary Search Tree — LeetCode 501 Python Solution
EasyTreeDepth-First SearchBinary Search TreeBinary Tree
- Problem
- #501
- Pattern
- Tree Traversal
- Reading time
- 5 min
- Source
- leetcode.com
The problem
Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it. If the tree has more than one mode, return them in any order.
Example
- Input
- root = [1,null,2,2]
- Output
- [2]
Python solution
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findMode(self, root: TreeNode) -> List[int]:
def dfs(root):
if root is None:
return
nonlocal mx, prev, ans, cnt
dfs(root.left)
cnt = cnt + 1 if prev == root.val else 1
if cnt > mx:
ans = [root.val]
mx = cnt
elif cnt == mx:
ans.append(root.val)
prev = root.val
dfs(root.right)
prev = None
mx = cnt = 0
ans = []
dfs(root)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(V+E) |
| Space | O(V) auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 501. Find Mode in Binary Search Tree is filed here because LeetCode tags it Tree, Binary Tree and Binary Search Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 501. Find Mode in Binary Search Tree?
- LeetCode 501. Find Mode in Binary Search Tree is rated Easy on LeetCode.
- What is the time complexity of LeetCode 501. Find Mode in Binary Search Tree?
- The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 501. Find Mode in Binary Search Tree?
- The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 501. Find Mode in Binary Search Tree cover?
- LeetCode 501. Find Mode in Binary Search Tree is tagged Tree, Depth-First Search, Binary Search Tree and Binary Tree on LeetCode.