C# || How To Get Smallest String Starting From Leaf Using C#
The following is a module with functions which demonstrates how to get smallest string starting from leaf using C#.
1. Smallest String Starting From Leaf – Problem Statement
You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters 'a' to 'z'.
Return the lexicographically smallest string that starts at a leaf of this tree and ends at the root.
As a reminder, any shorter prefix of a string is lexicographically smaller.
- For example,
"ab"is lexicographically smaller than"aba".
A leaf of a node is a node that has no children.
Example 1:
Input: root = [0,1,2,3,4,3,4]
Output: "dba"
Example 2:
Input: root = [25,1,3,1,3,0,2]
Output: "adz"
Example 3:
Input: root = [2,2,1,null,1,0,null,0]
Output: "abc"
2. Smallest String Starting From Leaf – Solution
The following is a solution which demonstrates how to convert get smallest string starting from leaf.
|
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 |
// ============================================================================ // Author: Kenneth Perkins // Date: Dec 1, 2024 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to get smallest string starting from leaf // ============================================================================ /** * 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 string SmallestFromLeaf(TreeNode root) { var smallestString = ""; var queue = new Queue<KeyValuePair<TreeNode, string>>(); // Enqueue root node to queue along with its value converted to a character queue.Enqueue(new KeyValuePair<TreeNode, string>(root, ((char)(root.val + 'a')).ToString())); // Perform BFS traversal until queue is empty while (queue.Count > 0) { // Pop the leftmost node and its corresponding string from queue var pair = queue.Dequeue(); var node = pair.Key; var currentString = pair.Value; // If current node is a leaf node if (node.left == null && node.right == null) { // Update smallest_string if it's empty or current string is smaller if (string.IsNullOrEmpty(smallestString)) { smallestString = currentString; } else { smallestString = currentString.CompareTo(smallestString) < 0 ? currentString : smallestString; } } // If current node has a left child, append it to queue if (node.left != null) { queue.Enqueue(new KeyValuePair<TreeNode, string>(node.left, (char)(node.left.val + 'a') + currentString)); } // If current node has a right child, append it to queue if (node.right != null) { queue.Enqueue(new KeyValuePair<TreeNode, string>(node.right, (char)(node.right.val + 'a') + currentString)); } } return smallestString; } }// 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:
"dba"
"adz"
"abc"
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
Leave a Reply