Kth Smallest Element in a BST

-
Credit to leetcode.com, this is a fun problem that with some understanding of the data structure (Binary Search Trees) can be solved relatively straightforward. Here it is:

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

The key insight is that if you traverse an BST using an in-order method, the elements of the tree will be, as the name implies, in-order, that is, they will be already sorted. Remember the 3 basic traversal orders:

Pre-Order:
  • Process current node
  • Process left node
  • Process right node
Post-Order:
  • Process the left node
  • Process the right node
  • Process the current node
In-Order:
  • Process the left node
  • Process the current node
  • Process the right node
So for this problem we'll traverse the tree in-order keeping a counter whenever we process the current node. The moment the counter gets to "k", we have found our element. Some minor checks to quit processing once we have found the solution (although that may not be necessary if we put some thought in it). Hope you enjoy!!!

    public class Solution
    {
        public int KthSmallest(TreeNode root, int k)
        {
            int retVal = -1;
            int currentIndex = 0;
            KthSmallestInternal(root, ref currentIndex, k, ref retVal);
            return retVal;
        }

        private bool KthSmallestInternal(TreeNode root, ref int currentIndex, int k, ref int retVal)
        {
            if (root == null) return false;
            if (KthSmallestInternal(root.left, ref currentIndex, k, ref retVal)) return true;
            currentIndex++;
            if (currentIndex == k)
            {
                retVal = root.val;
                return true;
            }
            if (KthSmallestInternal(root.right, ref currentIndex, k, ref retVal)) return true;
            return false;
        }
    }

Marcelo


Comments

  1. TarasMarch 20, 2016 at 10:42 AM

    Very concise and classical solution! In practice though, it can be slightly improved by using an explicit stack instead of implicit function invocation stack, since its limit is easier to control and less information would have to be stored on it. The version with explicit stack is usually called "imperative" and is a fun exercise :)

    ReplyDelete

Post a Comment

Popular posts from this blog

Advent of Code - Day 6, 2024: BFS and FSM

-
Image
To solve this Advent of Code (parts 1 and 2), I used Breadth-First Search (BFS) to keep moving the guard as well as Finite State Machine (FSM) to control the directions. This solves part 1 easily. Part 2 can be solved using the same technique, takes a little longer since you need to try every empty cell, but it eventually does the trick (takes a min or so). Code is down below, cheers, ACC. Day 6 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); List map = new List (); int startRow = 0; int startCol = 0; while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); map.Add(new StringBuilder(line)); int indexStart = line.IndexOf('^'); ...
Read more

Golang vs. C#: performance characteristics (simple case study)

-
Image
This is an interesting example to study the performance characteristics of Golang compared to C# for a very particular case (not generalized though).  The same code was written in C# and Golang (literally translated from one to the other). Below you'll be able to see the source code for both. The problem is a simple post-order DFS in a tree-like graph. The code in C# times out (TLE = Time Limited Exceeded). The code in Golang not only works but beats 100% of the other Golang submissions. Take a look the image below: Some potential reasons for the performance gains from Go in this particular example are: 1. Language and Runtime Differences:    Go is compiled directly to machine code, while C# typically runs on a virtual machine (CLR).    Go has a simpler runtime with less overhead compared to the .NET runtime.    Go's garbage collector is designed for low latency, which can lead to better performance in some scenarios. 2. Data Structures:    G...
Read more

Advent of Code - Day 7, 2024: Backtracking and Eval

-
Image
Problem today requires backtracking and eval (evaluating a mathematical expression in the format of a string). Glad that it used a left-2-right evaluation, makes for an easy parsing and not overly complicated evaluation function. Code is down below for parts 1 and 2. Cheers, ACC. Day 7 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; long retVal = 0; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); string[] parts1 = line.Split(':'); long target = Int64.Parse(parts1[0]); string[] numbers = parts1[1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); if (TryAll1(numbers, target, "", 0)) r...
Read more