Find Mode in Binary Search Tree

Problem Id: 501 Difficulty: Easy Tag: Tree


Intuition

Just do a inorder traversal and count the number of same continuously elements.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        self.max_count = 0
        self.current_count = 0
        self.current_element = None
        self.modes = []
        self._inorder(root)
        self._visit(TreeNode(None))
        return self.modes

    def _inorder(self, node):
        if node is None:
            return
        self._inorder(node.left)
        self._visit(node)
        self._inorder(node.right)

    def _visit(self, node):
        if self.current_element != node.val:
            if self.max_count < self.current_count:
                self.max_count = self.current_count
                self.modes = []
            if self.max_count == self.current_count:
                self.modes.append(self.current_element)
            self.current_element = node.val
            self.current_count = 0
        self.current_count += 1