December 2024 – My Programming Notes

Monthly Archives: December 2024

C# || How To Get Smallest String Starting From Leaf Using C#

December 01, 2024 admin No comments

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.





		
		
			2. Smallest String Starting From Leaf - Solution
			
C#
			
			// ============================================================================
//    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/
			
				
					
				
					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"

Monthly Archives: December 2024

C# || How To Get Smallest String Starting From Leaf Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories