Find Mode in Binary Search Tree

Description

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than or equal to the node's key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
• Both the left and right subtrees must also be binary search trees.

 

For example:
Given BST [1,null,2,2],

   1
    \
     2
    /
   2

 

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Solution(javascript)

const findMode = function (root) {
  let max = 0
  let prevNode = null
  const result = []
  const aux = (node, f) => {
    if (node) {
      aux(node.left, f)
      f(node)
      aux(node.right, f)
    }
  }
  aux(root, (node) => {
    if (prevNode && node.val === prevNode.val) {
      node.mode = prevNode.mode + 1
    } else {
      node.mode = 1
    }
    max = Math.max(node.mode, max)
    prevNode = node
  })
  aux(root, (node) => {
    if (node.mode === max) {
      result.push(node.val)
    }
  })
  return result
}