Python – Find the nodes in the tree that appear most frequently in all levels

I recently had a coding quiz that asked me to find the node in the tree that appears most frequently in all levels.

For example,

      a
     /  \
   c    a
  / \  / \
 c  a b   c

In this tree, a should be the answer as it appears on layers 0, 1 and 2.

I

tried using level order traversal to solve this problem, but I’m confused about how to track which level the node appears in.

How do I fix this, preferably using Python?

Tree Structure:

class TreeNode:
    def __init__(self, data = None):
        self.data = data
        self.left = None
        self.right = None

def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = TreeNode(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = TreeNode(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

As you traverse the tree, you use dict to track at which level each node type appears. This can be achieved by using the key as the node and the value as the set of levels to see the node.

def most_frequent_in_levels(tree):

counter = {}

def level_counter(tree, counter, level):
        if tree.data not in counter:
            counter[tree.data] = {level}
        else:
            counter[tree.data].add(level)

if tree.left:
            level_counter(tree.left, counter, level + 1)

if tree.right:
            level_counter(tree.right, counter, level + 1)

level_counter(tree, counter, 0)

return max(counter.keys(), key=lambda data: len(counter[data]))

Here is a working example.

tree = TreeNode(data='a')
tree.left, tree.right= TreeNode(data='a'), TreeNode(data='b')
tree.left.left, tree.left.right, tree.right.left = TreeNode(data='c'), TreeNode(data='c'), TreeNode(data='c')

# Which creates the following tree
#
#          a
#         /  \
#       a    b
#      / \  /
#     c  c c 

most_frequent_in_levels(tree) # 'a'