Find Mode in Binary Search Tree
The key idea
An in-order walk of a BST visits values in non-decreasing order, so every group of equal values arrives as one contiguous run. Track the length of the current run, the best run length seen, and the values that hit it — and you never need a hash map.
Problem
Given the root of a binary search tree (BST) with duplicates, return all the mode(s) — the value(s) that appear most often — in it.
If the tree has more than one mode, return them in any order.
Assume the BST is defined as: the left subtree of a node holds values less than or equal to the node's value, the right subtree holds values greater than or equal to the node's value, and both subtrees are themselves BSTs.
Follow up: Could you do it using O(1) extra space? (The recursion stack does not count.)
Constraints
- The number of nodes in the tree is in the range
[1, 10^4]. -10^5 <= Node.val <= 10^5
Examples
Input: root = [1,null,2,2]
Output: [2]
Input: root = [0]
Output: [0]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY