Skip to main content

Find occurrence of most repeated nodes in a binary tree

Here given code implementation process.

import java.util.HashMap;
/*
  Java program
  Find occurrence of most repeated nodes in a binary tree
*/
class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class BinarySearchTree
{
    public TreeNode root;
    public int result;
    public BinarySearchTree()
    {
        this.root = null;
        this.result = 0;
    }
    public void addNode(int data)
    {
        // Create a new node 
        TreeNode node = new TreeNode(data);
        if (this.root == null)
        {
            // When add a first node
            this.root = node;
        }
        else
        {
            // Get root of tree
            TreeNode find = this.root;

            // Find position to insert new node
            while (find != null)
            {
                if (find.data >= data)
                {
                    if (find.left == null)
                    {
                        find.left = node;
                        return;
                    }
                    else
                    {
                        // Visit left sub-tree
                        find = find.left;
                    }
                }
                else
                {
                    if (find.right == null)
                    {
                        find.right = node;
                        return;
                    }
                    else
                    {
                        // Visit right sub-tree
                        find = find.right;
                    }
                }
            }
        }
    }
    public void nodeCount(TreeNode node, HashMap < Integer, Integer > record)
    {
        if (node != null)
        {
            int count = 1;

            if (record.containsKey(node.data))
            {
                // Update frequency
                count = record.get(node.data) + 1;
            }
            if (this.result < count)
            {
                // When node occurs most time
                // Collect frequency
                this.result = count;
            }
            record.put(node.data, count);
            // Visit left and right sub-tree
            nodeCount(node.left, record);
            nodeCount(node.right, record);
        }
    }
    public void findMostRepeatedOccurrence()
    {
        if (this.root == null)
        {
            return;
        }
        this.result = 0;

        HashMap < Integer, Integer > record = new HashMap < Integer, Integer > ();
        
        this.nodeCount(this.root, record);
        
        // Display calculated result
        System.out.println(this.result);
    }
    public static void main(String[] args)
    {
        BinarySearchTree tree = new BinarySearchTree();

        // Input tree nodes
        int[] inputs = {
            6 , 2 , 1 , 0 , 3 , 2 , 7 , 3 , 3 , 4 , 0 , 1 , 7 , 3 , 9 , 8 , 1
        };
        // Get the number of elements
        int n = inputs.length;

        // Add tree elements
        for (int i = n - 1; i >= 0; --i)
        {
            tree.addNode(inputs[i]);
        }
        /*
            
            6 occurs = 1 time
            2 occurs = 2 time
            1 occurs = 3 time
            0 occurs = 2 time
            3 occurs = 4 time
            7 occurs = 2 time
            4 occurs = 1 time
            9 occurs = 1 time
            8 occurs = 1 time
            ------------------
            Most occurrence
            Result 4 [because 3 appears (4) times]
        */
        tree.findMostRepeatedOccurrence();
    }
}

Output

4
// Include header file
#include <iostream>
#include <unordered_map>

using namespace std;
/*
  C++ program
  Find occurrence of most repeated nodes in a binary tree
*/
class TreeNode
{
	public: int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinarySearchTree
{
	public: TreeNode *root;
	int result;
	BinarySearchTree()
	{
		this->root = NULL;
		this->result = 0;
	}
	void addNode(int data)
	{
		// Create a new node
		TreeNode *node = new TreeNode(data);
		if (this->root == NULL)
		{
			// When add a first node
			this->root = node;
		}
		else
		{
			// Get root of tree
			TreeNode *find = this->root;
			// Find position to insert new node
			while (find != NULL)
			{
				if (find->data >= data)
				{
					if (find->left == NULL)
					{
						find->left = node;
						return;
					}
					else
					{
						// Visit left sub-tree
						find = find->left;
					}
				}
				else
				{
					if (find->right == NULL)
					{
						find->right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find->right;
					}
				}
			}
		}
	}
	void nodeCount(TreeNode *node, unordered_map < int, int > record)
	{
		if (node != NULL)
		{
			int count = 1;
			if (record.find(node->data) != record.end())
			{
				// Update frequency
				count = record[node->data] + 1;
			}
			if (this->result < count)
			{
				// When node occurs most time
				// Collect frequency
				this->result = count;
			}
			record[node->data] = count;
			// Visit left and right sub-tree
			this->nodeCount(node->left, record);
			this->nodeCount(node->right, record);
		}
	}
	void findMostRepeatedOccurrence()
	{
		if (this->root == NULL)
		{
			return;
		}
		this->result = 0;
		unordered_map < int, int > record;
		this->nodeCount(this->root, record);
		// Display calculated result
		cout << this->result << endl;
	}
};
int main()
{
	BinarySearchTree *tree = new BinarySearchTree();
	// Input tree nodes
	int inputs[] = {
		6 , 2 , 1 , 0 , 3 , 2 , 7 , 3 , 3 , 4 , 0 , 1 , 7 , 3 , 9 , 8 , 1
	};
	// Get the number of elements
	int n = sizeof(inputs) / sizeof(inputs[0]);
	// Add tree elements
	for (int i = n - 1; i >= 0; --i)
	{
		tree->addNode(inputs[i]);
	}
	/*
	    6 occurs = 1 time
	    2 occurs = 2 time
	    1 occurs = 3 time
	    0 occurs = 2 time
	    3 occurs = 4 time
	    7 occurs = 2 time
	    4 occurs = 1 time
	    9 occurs = 1 time
	    8 occurs = 1 time
	    ------------------
	    Most occurrence
	    Result 4 [because 3 appears (4) times]
	*/
	tree->findMostRepeatedOccurrence();
	return 0;
}

Output

4
package main
import "fmt"
/*
  Go program
  Find occurrence of most repeated nodes in a binary tree
*/
type TreeNode struct {
	data int
	left * TreeNode
	right * TreeNode
}
func getTreeNode(data int) * TreeNode {
	var me *TreeNode = &TreeNode {}
	me.data = data
	me.left = nil
	me.right = nil
	return me
}
type BinarySearchTree struct {
	root * TreeNode
	result int
}
func getBinarySearchTree() * BinarySearchTree {
	var me *BinarySearchTree = &BinarySearchTree {}
	me.root = nil
	me.result = 0
	return me
}
func(this *BinarySearchTree) addNode(data int) {
	// Create a new node
	var node * TreeNode = getTreeNode(data)
	if this.root == nil {
		// When add a first node
		this.root = node
	} else {
		// Get root of tree
		var find * TreeNode = this.root
		// Find position to insert new node
		for (find != nil) {
			if find.data >= data {
				if find.left == nil {
					find.left = node
					return
				} else {
					// Visit left sub-tree
					find = find.left
				}
			} else {
				if find.right == nil {
					find.right = node
					return
				} else {
					// Visit right sub-tree
					find = find.right
				}
			}
		}
	}
}
func(this *BinarySearchTree) nodeCount(node * TreeNode, record map[int]int) {
	if node != nil {
		var count int = 1
		if _, found := record[node.data] ; found {
			// Update frequency
			count = record[node.data] + 1
		}
		if this.result < count {
			// When node occurs most time
			// Collect frequency
			this.result = count
		}
		record[node.data] = count
		// Visit left and right sub-tree
		this.nodeCount(node.left, record)
		this.nodeCount(node.right, record)
	}
}
func(this BinarySearchTree) findMostRepeatedOccurrence() {
	if this.root == nil {
		return
	}
	this.result = 0
	var record = make(map[int] int)
	this.nodeCount(this.root, record)
	// Display calculated result
	fmt.Println(this.result)
}
func main() {
	var tree * BinarySearchTree = getBinarySearchTree()
	// Input tree nodes
	var inputs = [] int {
		6,
		2,
		1,
		0,
		3,
		2,
		7,
		3,
		3,
		4,
		0,
		1,
		7,
		3,
		9,
		8,
		1,
	}
	// Get the number of elements
	var n int = len(inputs)
	// Add tree elements
	for i := n - 1 ; i >= 0 ; i-- {
		tree.addNode(inputs[i])
	}
	/*
	    6 occurs = 1 time
	    2 occurs = 2 time
	    1 occurs = 3 time
	    0 occurs = 2 time
	    3 occurs = 4 time
	    7 occurs = 2 time
	    4 occurs = 1 time
	    9 occurs = 1 time
	    8 occurs = 1 time
	    ------------------
	    Most occurrence
	    Result 4 [because 3 appears (4) times]
	*/
	tree.findMostRepeatedOccurrence()
}

Output

4
// Include namespace system
using System;
using System.Collections.Generic;
/*
  Csharp program
  Find occurrence of most repeated nodes in a binary tree
*/
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinarySearchTree
{
	public TreeNode root;
	public int result;
	public BinarySearchTree()
	{
		this.root = null;
		this.result = 0;
	}
	public void addNode(int data)
	{
		// Create a new node
		TreeNode node = new TreeNode(data);
		if (this.root == null)
		{
			// When add a first node
			this.root = node;
		}
		else
		{
			// Get root of tree
			TreeNode find = this.root;
			// Find position to insert new node
			while (find != null)
			{
				if (find.data >= data)
				{
					if (find.left == null)
					{
						find.left = node;
						return;
					}
					else
					{
						// Visit left sub-tree
						find = find.left;
					}
				}
				else
				{
					if (find.right == null)
					{
						find.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	public void nodeCount(TreeNode node, Dictionary < int, int > record)
	{
		if (node != null)
		{
			int count = 1;
			if (record.ContainsKey(node.data))
			{
				// Update frequency
				count = record[node.data] + 1;
				record[node.data] = count;
			}
			else
			{
				record.Add(node.data, count);
			}
			if (this.result < count)
			{
				// When node occurs most time
				// Collect frequency
				this.result = count;
			}
			// Visit left and right sub-tree
			this.nodeCount(node.left, record);
			this.nodeCount(node.right, record);
		}
	}
	public void findMostRepeatedOccurrence()
	{
		if (this.root == null)
		{
			return;
		}
		this.result = 0;
		Dictionary < int, int > record = new Dictionary < int, int > ();
		this.nodeCount(this.root, record);
		// Display calculated result
		Console.WriteLine(this.result);
	}
	public static void Main(String[] args)
	{
		BinarySearchTree tree = new BinarySearchTree();
		// Input tree nodes
		int[] inputs = {
			6 , 2 , 1 , 0 , 3 , 2 , 7 , 3 , 3 , 4 , 0 , 1 , 7 , 3 , 9 , 8 , 1
		};
		// Get the number of elements
		int n = inputs.Length;
		// Add tree elements
		for (int i = n - 1; i >= 0; --i)
		{
			tree.addNode(inputs[i]);
		}
		/*
		    6 occurs = 1 time
		    2 occurs = 2 time
		    1 occurs = 3 time
		    0 occurs = 2 time
		    3 occurs = 4 time
		    7 occurs = 2 time
		    4 occurs = 1 time
		    9 occurs = 1 time
		    8 occurs = 1 time
		    ------------------
		    Most occurrence
		    Result 4 [because 3 appears (4) times]
		*/
		tree.findMostRepeatedOccurrence();
	}
}

Output

4
<?php
/*
  Php program
  Find occurrence of most repeated nodes in a binary tree
*/
class TreeNode
{
	public $data;
	public $left;
	public $right;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class BinarySearchTree
{
	public $root;
	public $result;
	public	function __construct()
	{
		$this->root = NULL;
		$this->result = 0;
	}
	public	function addNode($data)
	{
		// Create a new node
		$node = new TreeNode($data);
		if ($this->root == NULL)
		{
			// When add a first node
			$this->root = $node;
		}
		else
		{
			// Get root of tree
			$find = $this->root;
			// Find position to insert new node
			while ($find != NULL)
			{
				if ($find->data >= $data)
				{
					if ($find->left == NULL)
					{
						$find->left = $node;
						return;
					}
					else
					{
						// Visit left sub-tree
						$find = $find->left;
					}
				}
				else
				{
					if ($find->right == NULL)
					{
						$find->right = $node;
						return;
					}
					else
					{
						// Visit right sub-tree
						$find = $find->right;
					}
				}
			}
		}
	}
	public	function nodeCount($node, $record)
	{
		if ($node != NULL)
		{
			$count = 1;
			if (array_key_exists($node->data, $record))
			{
				// Update frequency
				$count = $record[$node->data] + 1;
			}
			if ($this->result < $count)
			{
				// When node occurs most time
				// Collect frequency
				$this->result = $count;
			}
			$record[$node->data] = $count;
			// Visit left and right sub-tree
			$this->nodeCount($node->left, $record);
			$this->nodeCount($node->right, $record);
		}
	}
	public	function findMostRepeatedOccurrence()
	{
		if ($this->root == NULL)
		{
			return;
		}
		$this->result = 0;
		$record = array();
		$this->nodeCount($this->root, $record);
		// Display calculated result
		echo($this->result.
			"\n");
	}
}

function main()
{
	$tree = new BinarySearchTree();
	// Input tree nodes
	$inputs = array(6, 2, 1, 0, 3, 2, 7, 3, 3, 4, 0, 1, 7, 3, 9, 8, 1);
	// Get the number of elements
	$n = count($inputs);
	// Add tree elements
	for ($i = $n - 1; $i >= 0; --$i)
	{
		$tree->addNode($inputs[$i]);
	}
	/*
	    6 occurs = 1 time
	    2 occurs = 2 time
	    1 occurs = 3 time
	    0 occurs = 2 time
	    3 occurs = 4 time
	    7 occurs = 2 time
	    4 occurs = 1 time
	    9 occurs = 1 time
	    8 occurs = 1 time
	    ------------------
	    Most occurrence
	    Result 4 [because 3 appears (4) times]
	*/
	$tree->findMostRepeatedOccurrence();
}
main();

Output

4
/*
  Node JS program
  Find occurrence of most repeated nodes in a binary tree
*/
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	constructor()
	{
		this.root = null;
		this.result = 0;
	}
	addNode(data)
	{
		// Create a new node
		var node = new TreeNode(data);
		if (this.root == null)
		{
			// When add a first node
			this.root = node;
		}
		else
		{
			// Get root of tree
			var find = this.root;
			// Find position to insert new node
			while (find != null)
			{
				if (find.data >= data)
				{
					if (find.left == null)
					{
						find.left = node;
						return;
					}
					else
					{
						// Visit left sub-tree
						find = find.left;
					}
				}
				else
				{
					if (find.right == null)
					{
						find.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	nodeCount(node, record)
	{
		if (node != null)
		{
			var count = 1;
			if (record.has(node.data))
			{
				// Update frequency
				count = record.get(node.data) + 1;
			}
			if (this.result < count)
			{
				// When node occurs most time
				// Collect frequency
				this.result = count;
			}
			record.set(node.data, count);
			// Visit left and right sub-tree
			this.nodeCount(node.left, record);
			this.nodeCount(node.right, record);
		}
	}
	findMostRepeatedOccurrence()
	{
		if (this.root == null)
		{
			return;
		}
		this.result = 0;
		var record = new Map();
		this.nodeCount(this.root, record);
		// Display calculated result
		console.log(this.result);
	}
}

function main()
{
	var tree = new BinarySearchTree();
	// Input tree nodes
	var inputs = [6, 2, 1, 0, 3, 2, 7, 3, 3, 4, 0, 1, 7, 3, 9, 8, 1];
	// Get the number of elements
	var n = inputs.length;
	// Add tree elements
	for (var i = n - 1; i >= 0; --i)
	{
		tree.addNode(inputs[i]);
	}
	/*
	    6 occurs = 1 time
	    2 occurs = 2 time
	    1 occurs = 3 time
	    0 occurs = 2 time
	    3 occurs = 4 time
	    7 occurs = 2 time
	    4 occurs = 1 time
	    9 occurs = 1 time
	    8 occurs = 1 time
	    ------------------
	    Most occurrence
	    Result 4 [because 3 appears (4) times]
	*/
	tree.findMostRepeatedOccurrence();
}
main();

Output

4
#  Python 3 program
#  Find occurrence of most repeated nodes in a binary tree
class TreeNode :
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

class BinarySearchTree :
	def __init__(self) :
		self.root = None
		self.result = 0
	
	def addNode(self, data) :
		#  Create a new node
		node = TreeNode(data)
		if (self.root == None) :
			#  When add a first node
			self.root = node
		else :
			#  Get root of tree
			find = self.root
			#  Find position to insert new node
			while (find != None) :
				if (find.data >= data) :
					if (find.left == None) :
						find.left = node
						return
					else :
						#  Visit left sub-tree
						find = find.left
					
				else :
					if (find.right == None) :
						find.right = node
						return
					else :
						#  Visit right sub-tree
						find = find.right
					
				
			
		
	
	def nodeCount(self, node, record) :
		if (node != None) :
			count = 1
			if ((node.data in record.keys())) :
				#  Update frequency
				count = record.get(node.data) + 1
			
			if (self.result < count) :
				#  When node occurs most time
				#  Collect frequency
				self.result = count
			
			record[node.data] = count
			#  Visit left and right sub-tree
			self.nodeCount(node.left, record)
			self.nodeCount(node.right, record)
		
	
	def findMostRepeatedOccurrence(self) :
		if (self.root == None) :
			return
		
		self.result = 0
		record = dict()
		self.nodeCount(self.root, record)
		#  Display calculated result
		print(self.result)
	

def main() :
	tree = BinarySearchTree()
	#  Input tree nodes
	inputs = [6, 2, 1, 0, 3, 2, 7, 3, 3, 4, 0, 1, 7, 3, 9, 8, 1]
	#  Get the number of elements
	n = len(inputs)
	i = n - 1
	#  Add tree elements
	while (i >= 0) :
		tree.addNode(inputs[i])
		i -= 1
	
	#    6 occurs = 1 time
	#    2 occurs = 2 time
	#    1 occurs = 3 time
	#    0 occurs = 2 time
	#    3 occurs = 4 time
	#    7 occurs = 2 time
	#    4 occurs = 1 time
	#    9 occurs = 1 time
	#    8 occurs = 1 time
	#    ------------------
	#    Most occurrence
	#    Result 4 [because 3 appears (4) times]
	tree.findMostRepeatedOccurrence()

if __name__ == "__main__": main()

Output

4
#  Ruby program
#  Find occurrence of most repeated nodes in a binary tree
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(data) 
		self.data = data
		self.left = nil
		self.right = nil
	end

end

class BinarySearchTree 
	# Define the accessor and reader of class BinarySearchTree
	attr_reader :root, :result
	attr_accessor :root, :result
	def initialize() 
		self.root = nil
		self.result = 0
	end

	def addNode(data) 
		#  Create a new node
		node = TreeNode.new(data)
		if (self.root == nil) 
			#  When add a first node
			self.root = node
		else
 
			#  Get root of tree
			find = self.root
			#  Find position to insert new node
			while (find != nil) 
				if (find.data >= data) 
					if (find.left == nil) 
						find.left = node
						return
					else
 
						#  Visit left sub-tree
						find = find.left
					end

				else
 
					if (find.right == nil) 
						find.right = node
						return
					else
 
						#  Visit right sub-tree
						find = find.right
					end

				end

			end

		end

	end

	def nodeCount(node, record) 
		if (node != nil) 
			count = 1
			if (record.key?(node.data)) 
				#  Update frequency
				count = record[node.data] + 1
			end

			if (self.result < count) 
				#  When node occurs most time
				#  Collect frequency
				self.result = count
			end

			record[node.data] = count
			#  Visit left and right sub-tree
			self.nodeCount(node.left, record)
			self.nodeCount(node.right, record)
		end

	end

	def findMostRepeatedOccurrence() 
		if (self.root == nil) 
			return
		end

		self.result = 0
		record = Hash.new()
		self.nodeCount(self.root, record)
		#  Display calculated result
		print(self.result, "\n")
	end

end

def main() 
	tree = BinarySearchTree.new()
	#  Input tree nodes
	inputs = [6, 2, 1, 0, 3, 2, 7, 3, 3, 4, 0, 1, 7, 3, 9, 8, 1]
	#  Get the number of elements
	n = inputs.length
	i = n - 1
	#  Add tree elements
	while (i >= 0) 
		tree.addNode(inputs[i])
		i -= 1
	end

	#    6 occurs = 1 time
	#    2 occurs = 2 time
	#    1 occurs = 3 time
	#    0 occurs = 2 time
	#    3 occurs = 4 time
	#    7 occurs = 2 time
	#    4 occurs = 1 time
	#    9 occurs = 1 time
	#    8 occurs = 1 time
	#    ------------------
	#    Most occurrence
	#    Result 4 [because 3 appears (4) times]
	tree.findMostRepeatedOccurrence()
end

main()

Output

4

import scala.collection.mutable._;
/*
  Scala program
  Find occurrence of most repeated nodes in a binary tree
*/
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class BinarySearchTree(var root: TreeNode,
	var result: Int)
{
	def this()
	{
		this(null, 0);
	}
	def addNode(data: Int): Unit = {
		// Create a new node
		var node: TreeNode = new TreeNode(data);
		if (this.root == null)
		{
			// When add a first node
			this.root = node;
		}
		else
		{
			// Get root of tree
			var find: TreeNode = this.root;
			// Find position to insert new node
			while (find != null)
			{
				if (find.data >= data)
				{
					if (find.left == null)
					{
						find.left = node;
						return;
					}
					else
					{
						// Visit left sub-tree
						find = find.left;
					}
				}
				else
				{
					if (find.right == null)
					{
						find.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	def nodeCount(node: TreeNode, record: HashMap[Int, Int]): Unit = {
		if (node != null)
		{
			var count: Int = 1;
			if (record.contains(node.data))
			{
				// Update frequency
				count = record.get(node.data).get + 1;
			}
			if (this.result < count)
			{
				// When node occurs most time
				// Collect frequency
				this.result = count;
			}
			record.addOne(node.data, count);
			// Visit left and right sub-tree
			nodeCount(node.left, record);
			nodeCount(node.right, record);
		}
	}
	def findMostRepeatedOccurrence(): Unit = {
		if (this.root == null)
		{
			return;
		}
		this.result = 0;
		var record: HashMap[Int, Int] = new HashMap[Int, Int]();
		this.nodeCount(this.root, record);
		// Display calculated result
		println(this.result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinarySearchTree = new BinarySearchTree();
		// Input tree nodes
		var inputs: Array[Int] = Array(6, 2, 1, 0, 3, 2, 7, 3, 3, 4, 0, 1, 7, 3, 9, 8, 1);
		// Get the number of elements
		var n: Int = inputs.length;
		var i: Int = n - 1;
		// Add tree elements
		while (i >= 0)
		{
			tree.addNode(inputs(i));
			i -= 1;
		}
		/*
		    6 occurs = 1 time
		    2 occurs = 2 time
		    1 occurs = 3 time
		    0 occurs = 2 time
		    3 occurs = 4 time
		    7 occurs = 2 time
		    4 occurs = 1 time
		    9 occurs = 1 time
		    8 occurs = 1 time
		    ------------------
		    Most occurrence
		    Result 4 [because 3 appears (4) times]
		*/
		tree.findMostRepeatedOccurrence();
	}
}

Output

4
import Foundation;
/*
  Swift 4 program
  Find occurrence of most repeated nodes in a binary tree
*/
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinarySearchTree
{
	var root: TreeNode? ;
	var result: Int;
	init()
	{
		self.root = nil;
		self.result = 0;
	}
	func addNode(_ data: Int)
	{
		// Create a new node
		let node: TreeNode = TreeNode(data);
		if (self.root == nil)
		{
			// When add a first node
			self.root = node;
		}
		else
		{
			// Get root of tree
			var find: TreeNode? = self.root;
			// Find position to insert new node
			while (find  != nil)
			{
				if (find!.data >= data)
				{
					if (find!.left == nil)
					{
						find!.left = node;
						return;
					}
					else
					{
						// Visit left sub-tree
						find = find!.left;
					}
				}
				else
				{
					if (find!.right == nil)
					{
						find!.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find!.right;
					}
				}
			}
		}
	}
	func nodeCount(_ node: TreeNode? , _ record : inout[Int : Int])
	{
		if (node  != nil)
		{
			var count: Int = 1;
			if (record.keys.contains(node!.data))
			{
				// Update frequency
				count = record[node!.data]! + 1;
			}
			if (self.result < count)
			{
				// When node occurs most time
				// Collect frequency
				self.result = count;
			}
			record[node!.data] = count;
			// Visit left and right sub-tree
			self.nodeCount(node!.left, &record);
			self.nodeCount(node!.right, &record);
		}
	}
	func findMostRepeatedOccurrence()
	{
		if (self.root == nil)
		{
			return;
		}
		self.result = 0;
		var record: [Int : Int] = [Int : Int]();
		self.nodeCount(self.root, &record);
		// Display calculated result
		print(self.result);
	}
}
func main()
{
	let tree: BinarySearchTree = BinarySearchTree();
	// Input tree nodes
	let inputs: [Int] = [6, 2, 1, 0, 3, 2, 7, 3, 3, 4, 0, 1, 7, 3, 9, 8, 1];
	// Get the number of elements
	let n: Int = inputs.count;
	var i: Int = n - 1;
	// Add tree elements
	while (i >= 0)
	{
		tree.addNode(inputs[i]);
		i -= 1;
	}
	/*
	    6 occurs = 1 time
	    2 occurs = 2 time
	    1 occurs = 3 time
	    0 occurs = 2 time
	    3 occurs = 4 time
	    7 occurs = 2 time
	    4 occurs = 1 time
	    9 occurs = 1 time
	    8 occurs = 1 time
	    ------------------
	    Most occurrence
	    Result 4 [because 3 appears (4) times]
	*/
	tree.findMostRepeatedOccurrence();
}
main();

Output

4
/*
  Kotlin program
  Find occurrence of most repeated nodes in a binary tree
*/
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	var root: TreeNode ? ;
	var result: Int;
	constructor()
	{
		this.root = null;
		this.result = 0;
	}
	fun addNode(data: Int): Unit
	{
		// Create a new node
		val node: TreeNode = TreeNode(data);
		if (this.root == null)
		{
			// When add a first node
			this.root = node;
		}
		else
		{
			// Get root of tree
			var find: TreeNode ? = this.root;
			// Find position to insert new node
			while (find != null)
			{
				if (find.data >= data)
				{
					if (find.left == null)
					{
						find.left = node;
						return;
					}
					else
					{
						// Visit left sub-tree
						find = find.left;
					}
				}
				else
				{
					if (find.right == null)
					{
						find.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	fun nodeCount(node: TreeNode ? , record : HashMap < Int, Int > ): Unit
	{
		if (node != null)
		{
			var count: Int = 1;
			if (record.containsKey(node.data))
			{
				// Update frequency
				count = record.getValue(node.data) + 1;
			}
			if (this.result < count)
			{
				// When node occurs most time
				// Collect frequency
				this.result = count;
			}
			record.put(node.data, count);
			// Visit left and right sub-tree
			this.nodeCount(node.left, record);
			this.nodeCount(node.right, record);
		}
	}
	fun findMostRepeatedOccurrence(): Unit
	{
		if (this.root == null)
		{
			return;
		}
		this.result = 0;
		val record: HashMap < Int, Int > = HashMap < Int, Int > ();
		this.nodeCount(this.root, record);
		// Display calculated result
		println(this.result);
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinarySearchTree = BinarySearchTree();
	// Input tree nodes
	val inputs: Array < Int > = arrayOf(6, 2, 1, 0, 3, 2, 7, 3, 3, 4, 0, 1, 7, 3, 9, 8, 1);
	// Get the number of elements
	val n: Int = inputs.count();
	var i: Int = n - 1;
	// Add tree elements
	while (i >= 0)
	{
		tree.addNode(inputs[i]);
		i -= 1;
	}
	/*
	    6 occurs = 1 time
	    2 occurs = 2 time
	    1 occurs = 3 time
	    0 occurs = 2 time
	    3 occurs = 4 time
	    7 occurs = 2 time
	    4 occurs = 1 time
	    9 occurs = 1 time
	    8 occurs = 1 time
	    ------------------
	    Most occurrence
	    Result 4 [because 3 appears (4) times]
	*/
	tree.findMostRepeatedOccurrence();
}

Output

4
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment