Monthly Archives: October 2024
C# || How To Find Mode In Binary Search Tree Using C#
The following is a module with functions which demonstrates how to find mode in binary search tree using C#.
1. Find Mode – Problem Statement
Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.
If the tree has more than one mode, return them in any order.
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.
Example 1:
Input: root = [1,null,2,2]
Output: [2]
Example 2:
Input: root = [0]
Output: [0]
2. Find Mode – Solution
The following is a solution which demonstrates how to find mode in binary search tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
// ============================================================================ // Author: Kenneth Perkins // Date: Oct 1, 2024 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find mode in binary search tree // ============================================================================ /** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public int[] FindMode(TreeNode root) { int maxStreak = 0; int currStreak = 0; int currNum = 0; var ans = new List<int>(); TreeNode curr = root; while (curr != null) { if (curr.left != null) { // Find the friend TreeNode friend = curr.left; while (friend.right != null) { friend = friend.right; } friend.right = curr; // Delete the edge after using it TreeNode left = curr.left; curr.left = null; curr = left; } else { // Handle the current node int num = curr.val; if (num == currNum) { currStreak++; } else { currStreak = 1; currNum = num; } if (currStreak > maxStreak) { ans = new List<int>(); maxStreak = currStreak; } if (currStreak == maxStreak) { ans.Add(num); } curr = curr.right; } } int[] result = new int[ans.Count]; for (int i = 0; i < ans.Count; i++) { result[i] = ans[i]; } return result; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
[2]
[0]