[Programming Problem] Closest Binary Search Tree Value I and II

Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4

[Problem Link]

Since this is a BST, if the current node is larger than target, we look in the left subtree, else in the right subtree. In the end we simply return the value we get back from our recursion or the current node value depending on whichever one is closer to target. Remember to account for null values when we encounter a leaf node.

Time complexity is O(lgN)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {number}
 */
var closestValue = function(root, target) {
    if (!root) return null;
 
    let minNext;
    if (root.val > target) minNext = closestValue(root.left, target);
    else minNext = closestValue(root.right, target); 
 
    let minCurrDist = Math.abs(root.val-target);
    let minNextDist = minNext !== null ? Math.abs(minNext-target) : Number.MAX_VALUE;
 
    return minNextDist < minCurrDist ? minNext: root.val;
};

Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

[Problem Link]

Traverse the full tree and keep storing closest distances (to target) in a priority queue. In the end, pop k number of elements from the queue and return the result. Note, the priority queue will be ordered based on distance (and not on the node values).

Time complexity will be O(NLgN), insert N items into a heap.
If we decide to keep the heap size k, it goes to O(NLgK).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
class Node implements Comparable<Node> {
    int val;
    double dist;
    public Node(int val, double dist) {
        this.val = val;
        this.dist = dist;
    }
    public int compareTo(Node o) {
        return this.dist < o.dist ? -1 : 1;
    }
}
 
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        PriorityQueue<Node> q = new PriorityQueue<Node>();
        traverseBST(root, target, q);
        List<Integer> ret = new ArrayList<Integer>();
        for ( int i = 0 ; i < k ; i++ ) {
            ret.add(q.poll().val);
        }
        return ret;
    }
 
    public void traverseBST(TreeNode root, double target, PriorityQueue<Node> q) {
        if ( root == null )
            return;
        q.offer(new Node(root.val, Math.abs(root.val - target)));        
        traverseBST(root.left, target, q);
        traverseBST(root.right, target, q);        
    }
}

Another approach would be to traverse (inOrder) through the tree to build a sorted array (i.e. O(n)). Then we use two pointers to get the subarray which has numbers closest to k (i.e. another O(n) time complexity).

Total time complexity for this is: O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @param {number} k
 * @return {number[]}
 */
 
function inOrder(root, arr) {
    if (!root) return;
 
    inOrder(root.left, arr);
    arr.push(root.val);
    inOrder(root.right, arr);
}
 
var closestKValues = function(root, target, k) {
    let ret = [];
    inOrder(root, ret);
    let i = 0;
    let j = ret.length - 1;
    while ((j-i+1) != k) {
        let iDist = Math.abs(ret[i] - target);
        let jDist = Math.abs(ret[j] - target);
        if ( iDist < jDist ) j--
        else i++
    }    
    let finalRet = [];
    for ( let start = i ; start <= j ; start++ ) finalRet.push(ret[start]);
    return finalRet;
};

1,624 thoughts on “[Programming Problem] Closest Binary Search Tree Value I and II

  1. I wish to convey my respect for your generosity supporting those individuals that have the need for guidance on this one subject matter. Your personal dedication to getting the message all through had been incredibly beneficial and have continually helped most people much like me to achieve their endeavors. This helpful publication implies a whole lot to me and far more to my office workers. With thanks; from all of us.

  2. I wish to voice my respect for your kindness supporting individuals that must have guidance on this particular matter. Your very own dedication to getting the message all over appeared to be exceedingly interesting and has in every case allowed somebody just like me to attain their desired goals. Your amazing valuable help and advice denotes a great deal to me and a whole lot more to my fellow workers. With thanks; from all of us.

  3. I am only writing to make you understand what a fine encounter my friend’s child went through using the blog. She even learned plenty of pieces, which include what it is like to have a marvelous helping style to get many others with ease fully understand a variety of advanced things. You undoubtedly did more than people’s desires. I appreciate you for giving such important, dependable, educational as well as unique guidance on this topic to Gloria.

  4. I’m also writing to make you understand of the really good encounter my wife’s princess obtained using the blog. She figured out a lot of details, with the inclusion of what it’s like to have an excellent helping mindset to get a number of people quite simply fully grasp various impossible issues. You undoubtedly did more than her desires. Many thanks for imparting the necessary, dependable, edifying and also unique tips on your topic to Julie.

  5. Needed to send you one bit of observation to help give many thanks yet again for all the awesome methods you have contributed above. It’s really particularly generous with people like you giving without restraint just what many of us could have marketed for an electronic book to earn some profit for themselves, especially considering that you could have done it in case you considered necessary. Those advice likewise worked as the easy way to comprehend most people have a similar interest really like my own to figure out great deal more with regards to this issue. I’m certain there are some more fun instances in the future for individuals that read carefully your website.

  6. I happen to be commenting to let you understand what a cool discovery our girl developed visiting the blog. She realized numerous details, most notably what it is like to have an amazing teaching mindset to have others without hassle learn some advanced topics. You really exceeded readers’ desires. Thank you for showing these warm and helpful, trusted, informative and as well as fun tips on your topic to Lizeth.

  7. I precisely had to thank you very much yet again. I do not know the things I could possibly have used in the absence of the secrets provided by you relating to my concern. It was actually an absolute daunting dilemma for me personally, but observing a expert tactic you managed that took me to jump for fulfillment. I am thankful for the guidance and thus wish you realize what a powerful job you are getting into instructing men and women by way of a web site. Most likely you haven’t met all of us.

  8. I must point out my love for your generosity giving support to men and women who really want guidance on the theme. Your real dedication to getting the solution all over ended up being extremely valuable and has really empowered folks much like me to achieve their objectives. Your amazing valuable instruction denotes so much to me and even more to my peers. Regards; from all of us.

  9. I wish to express some thanks to the writer for rescuing me from this particular incident. As a result of looking through the search engines and meeting things which are not beneficial, I assumed my life was over. Living without the strategies to the issues you’ve fixed through your entire review is a critical case, and ones which may have in a negative way affected my career if I had not come across your website. Your actual knowledge and kindness in handling every part was helpful. I am not sure what I would have done if I hadn’t encountered such a step like this. It’s possible to now look forward to my future. Thank you so much for your professional and effective guide. I will not hesitate to suggest your site to any individual who needs to have assistance on this subject matter.

  10. I wanted to compose you that very small note to say thank you yet again for your personal pretty secrets you’ve contributed on this site. This is unbelievably open-handed of people like you to provide unhampered all that numerous people would have offered for an e book to earn some dough on their own, particularly now that you might have done it if you wanted. These pointers likewise acted to be a great way to know that many people have similar passion similar to my own to see a whole lot more when considering this matter. I believe there are thousands of more fun times in the future for folks who read through your site.

  11. I must voice my gratitude for your kindness supporting people that actually need help with this one theme. Your special dedication to getting the solution all-around turned out to be unbelievably functional and have frequently helped those just like me to get to their pursuits. Your amazing informative report implies a whole lot a person like me and somewhat more to my fellow workers. Thanks a lot; from everyone of us.

  12. I would like to express my admiration for your generosity supporting people who really want help on your concept. Your real dedication to passing the solution all over turned out to be extremely effective and have allowed regular people much like me to attain their objectives. Your warm and friendly publication means a great deal to me and far more to my fellow workers. With thanks; from everyone of us.

  13. I wish to express my appreciation to this writer for rescuing me from this setting. After surfing around through the internet and seeing views that were not helpful, I figured my entire life was well over. Existing devoid of the solutions to the difficulties you have solved through your good review is a serious case, as well as those which may have negatively damaged my entire career if I hadn’t noticed your site. The know-how and kindness in taking care of all the stuff was valuable. I don’t know what I would have done if I hadn’t come across such a step like this. I can at this time relish my future. Thanks for your time so much for this skilled and effective help. I will not be reluctant to propose the sites to anybody who needs to have guide about this topic.

  14. I precisely wished to thank you very much yet again. I am not sure the things I would have gone through without the creative concepts contributed by you regarding this theme. It had become a very depressing case in my circumstances, but seeing a professional fashion you resolved that took me to leap over delight. I am grateful for the service and even believe you are aware of an amazing job that you’re providing educating most people via your site. I’m certain you have never got to know any of us.

  15. I precisely desired to say thanks once more. I’m not certain the things that I would’ve taken care of in the absence of the actual secrets discussed by you about such a area of interest. Previously it was a very challenging problem in my circumstances, nevertheless observing the very specialized style you dealt with the issue took me to cry with happiness. I am just grateful for the service as well as trust you know what an amazing job you are putting in training most people using a blog. Most likely you’ve never met all of us.

  16. A lot of thanks for all of your effort on this site. Kim take interest in setting aside time for investigations and it’s obvious why. Many of us know all relating to the powerful means you produce sensible steps by means of the web site and as well invigorate participation from others about this point plus my simple princess is certainly being taught a great deal. Take pleasure in the remaining portion of the new year. You have been carrying out a dazzling job.

  17. I precisely had to appreciate you yet again. I’m not certain what I could possibly have undertaken in the absence of these advice shared by you concerning such question. It was before a real depressing issue for me personally, but considering the very professional technique you resolved the issue forced me to jump for contentment. Now i’m happy for the guidance as well as hope that you comprehend what an amazing job you are accomplishing instructing many people all through your website. Most likely you have never met any of us.

  18. I have to voice my passion for your kind-heartedness in support of persons that should have help with your area of interest. Your personal commitment to getting the solution up and down had been wonderfully helpful and have empowered professionals just like me to realize their dreams. This warm and helpful help indicates much a person like me and even further to my colleagues. With thanks; from everyone of us.

  19. You’ve made some decent points there. I checked on the web to learn more about the issue and
    found most people will go along with your views
    on this site.

  20. Откройте для себя мир релакса и уюта в термальном комплексе Termburg. Загляните на termburg.ru и забронируйте свой отдых уже сегодня!

  21. Adana ilinde hizmet veren, çoğunlukla genç ve orta yaşlı bayanların para karşılığı yaptığı meslektir.
    Adana Escort olarak anal, oral, masaj, ucuz vb gibi hizmet için resmi ve güvenilir
    web site olan http://www.adanaescort.com siz ziyaretçilere fotoğraflı ve
    açıklamalı olarak bayan portföyü sunar.

  22. I simply could not depart your website before suggesting that I extremely loved the usual information a person supply
    for your visitors? Is gonna be back often to check up on new posts

  23. فن آموزان اصفهان یکی از معتبرترین و
    بهترین آموزشگاه های فنی حرفه ای اصفهان بوده که دوره های گوناگونی در حوزه برق، الکترونیک، کنترل ابزار
    دقیق، صنایع خودرو، صنایع چوب، صنایع
    فلزی، تعمیرات، تاسیسات و … زیر
    نظر سازمان فنی حرفه ای کشور، توسط بهترین اساتید، به صورت عملی و پروژه محور برگزار می کند.
    این دوره ها بسیار فراتر از یک کلاس آموزشی ساده بوده و
    شما را از ابتدایِ مسیر یادگیری تا رسیدن
    به مرحله ورود به بازار کار، کسب
    درآمد و راه اندازی کسب و کار شخصی هدایت
    می کنند. ثبت نام کلاسهای فنی حرفه ای اصفهان در این
    آموزشگاه، بهترین انتخاب شغلی و تحصیلی برای
    شما عزیزان است چرا که می توانید با شرکت در این کلاس ها، انواع مهارت های فنی به روز و کاربردی
    و سودآور را در کارگاه های پیشرفته و مدرن یاد بگیرید و با جدیدترین تجهیزات و ابزارهای فنی آشنا شده و طرز کار
    آن ها را بیاموزید. به علاوه؛ در
    پایان همه دوره های فنی حرفه ای
    اصفهان که در این آموزشگاه برگزار می شود، شما می توانید با قبولی
    در آزمون های مربوطه، مدرک فنی و حرفه
    ای معتبر و قابل ترجمه در رشته مورد نظر
    خود دریافت کنید.

  24. جوش تیگ یا همان آرگون یکی از متداول ترین روش‌های
    جوشکاری ذوبی محسوب میشود که در
    آن از گاز آرگون به عنوان گاز محافظ برای
    حفاظت از قطعه در مقابل اکسیداسیون و حرارت استفاده می‌شود.
    جوش آرگون به دلیل داشتن مزایایی چون دقت بالا، قابلیت جوشکاری فلزات مختلف، کیفیت بالای جوش
    و سرعت بالا در بسیاری از صنایع مختلف از جمله صنایع نفت و گاز، صنایع دریایی، صنایع خودرو

  25. دلکو که از واژه انگلیسی
    Distributor گرفته شده است، در واقع یک قطعه مکانیکی مهم در خودرو های کاربراتوری
    محسوب می شود که مسئولیت توزیع
    و پخش جریان برق بین شمع های اتومبیل را بر عهده دارد.
    با توجه به عملکرد مهم این قطعه در سیستم سوخت رسانی،
    هر مکانیک و برقکار خودوریی باید دلکو را بشناسد و وظیفه
    آن را در خودرو ها بداند. به همین منظور، در این
    مقاله از فن آموزان ضمن تعریف دلکو، با قطعات به کار رفته در آن آشنا
    شده و وظیفه آن را بررسی می کنیم.

  26. درجه دو نیز شامل آموزش سیم کشی خودرو می باشد اما چون اصول اولیه کارکرد ماشین های پی تی
    پی یا ماشین های معمولی با ماشین های مالتی پلکس تفاوت دارد قائدتا نقشه خوانی آنها هم متفاوت
    است. به همین دلیل شبکه های مختلف ماشین های
    مالتی پلکس را در دوره آموزش صفر تا صد برق خودرو درجه یک بصورت کامل و حرفه ای یاد می گیرید.
    این مباحث با ماکس شروع
    می شود که اکو ماکس، سی ای سی CEC
    و سازه پویش و ب

  27. از این اطلاعات استفاده می کنیم ؛ تعویض قطعه؛ مدارات پرکاربرد که در بردها استفاده می
    شود را یاد می گیرید که شامل مدارات تغذیه، مدارات راه انداز یا درایو،
    مدرات مربوط به سنسور ها و… می باشد؛ و نهایتا این مدارات کنار هم

  28. ن آموزان بصورت کامل و عملی یاد می گیرید با دستگاه
    اسپرسو و تجهیزات کافی شاپ و قهوه هایی که از طریق دستگاه تهیه می شود کار کنید و
    بتوانید انواع مختلف قهوه ها را سرو کنید؛ اینکه چگونه یک قهوه ست
    کنید؛ چگونه قهوه ای درست کنید که مزه متعادلی داشته باشد؛ نحوه فوم گیری شیر
    و بحث لته آرت و پترن های

  29. ا توجه به اینکه برد، اصلی ترین قطعه
    در تمامی پکیج ها می باشد، در این دوره به صورت تخصصی این قطعه
    و نحوع عملکرد آن توضیح داده می شود و مشکلات مربوط به آن با
    جزئیات بیشتری بررسی می
    شود.

    مدرس دوره نصب و تعمیرات پکیج مهندس رضا فیروز بخت هستند با سابقه 25 سال کار تاسیسات از جمله موتورخانه ، تعمیرات پکیج ،
    کولرهای گازی ، چیلر ، وی آر اف ، انواع لوله کشی
    و تمامی رشته

  30. مناسب آن پروژه اجرا می شود.

    در بخش سوم اموزش نصب دوربین به تنظیمات و تجهیزات جانبی دستگاه ضبط کننده می پردازیم.
    و به اتصالات ، مشخصات و تجهیزات جانبی دستگاه ضبط کننده
    را بررسی می کنیم.

    به کارآموزان آموزش داده می شود با ابزارهای موجود در کارگاه
    فیش سوکت و کابل درست کنند که از آنها در بخش عملی استفاده می شود.

    در بخش بعدی با استفاده از تجهیزاتی که کارآموزان مهیا کرده اند تنظیمات مربوط به دستگاه های ضب

  31. می تواند مهارت های عملی و
    دانش علمی شما را در این کار تقویت نموده و آموزش تعمیرات کولر گازی از صفر تا
    صد را فراگیرید. آموزشگاه فن آموزان با سابقه
    ای درخشان اقدام به برگزاری دوره تعمیرات کولر گازی
    در تهران می نماید و علاوه بر آن امکان
    شرکت در کلاس های آموزشی
    تعمیر کولر گازی به صورت آنلاین و برای افرادی که امکان شرکت در کلاس
    های حضوری را ندارند وجود دارد.

    این آموزشگاه تحت نظارت سازمان فنی و حرفه
    ای فعالیت نموده و پس از اتمام
    دوره به کارآموزان مدرک معتبر فنی و حرفه ای تعمیرات اسپیلت و کولر گازی اعطا می نماید.

  32. با یادگیری مباحث ecu می توانید به راحتی بر انواع مدارهای ایسیو و کیلومترها
    در اتومبیل های داخلی و خارجی و حتی وسایل نقلیه سنگین تسلط پیدا کنید.

    بحث بازار کار این رشته را بخواهیم مطرح کنیم در کل ایران شاید ده یا 15 نفر هم نباشند که این کار
    را بصورت حرفه ای انجام بدهند. حتی در خارج از کشور و در سطح دنیا هم این کار خیلی پولساز است.

  33. Saya telah mengikuti diskusi tentang topik ini untuk sementara waktu, tapi postingan Anda adalah hembusan udara segar. Jelas Anda telah melakukan pekerjaan rumah Anda, dan wawasan Anda tepat sasaran. Ini memicu beberapa ide dalam pikiran saya. Apakah Anda keberatan jika saya membagikan pandangan berbeda untuk diskusi?

  34. مباحث دزدگیر از سیم های دزدگیر شروع می شود.
    دزدگیر ماشین وسیله ای هست که سیم های زیادی دارد.
    اگر کارآموز برق ماشین را بشناسد و
    شرایط را بتواند درک کند میتواند این سیم ها را نصب کند که در کلاس آموزش صفر تا صد نصب دزدگیر
    ماشین تک تک سیم ها کامل یاد داده می شود
    و رنگها

  35. ث روشنایی محیط و اینکه به چه شکل
    روشنایی را هوشمند کنید ، بحث کنترل گرمایش و سرمایش ،
    بحث سیستم های ورودی-خروجی یا همان اکسس کنترل ها ، بحث دزدگیر ، دوربین
    و اعلام حریق و… را بصورت هوشم

  36. ال جی ، آموزش تعمیر ماشین لباسشویی بکو ، تعمیر ماشین لباسشویی آبسال
    ، تعمیر لباسشویی اسنوا و…
    تمرکز دارد.

    این دوره از پایه تا پیشرفته مباحث تعمیرات لباسشویی را در برمی گیرد و هم برای افرادی که پیش زمینه ای در
    این حرفه نیز ندارند کاربردی است و هم برای افرادی که می خواهند دانش خود را در زمینه مهارتهای پیشرفته تر تعمیر ماشین لباسشویی ارتقاء دهند.

  37. ا پیشرفته برای تمامی سنین بدون محدودیت
    و نیاز خاص به مدرک یا پیش زمینه آموزشی اشاره کرد.
    همچنین کارآموزان با شرکت در این دوره ها
    می توانند با تجهیزات آموزشی از نزدیک کار کنند تا مهارت لازم جهت کارهای عملی بدست آورند و پس از پایان دوره مشاوره لازم برای ورود به بازار کار را
    دریافت کرده و با در دست داشتن مدرک معت

  38. نر قالی بافی، یکی از هنرهای دستی قدیمی
    است که در بین ایرانیان، به خصوص خانم‌های خانه‌دار، رایج بوده است.
    با یادگیری این حرفه، شما می‌توانید قالی را به عنوان
    یک منبع درآمد خوب برای خودتان در نظر
    بگیرید. حتی اگر شما برای تفریح، شروع
    به بافتن یک قالی کنید و آن
    را به اتمام برسانید، متوجه خواهید شد که
    چه درآمد خوبی برای شما میتواند به همراه داشته باشد.

  39. ولات را با استفاده از جنس چرم بدوزند.

    این دوره مناسب : فعالان و علاقه‌ مندان حوزه مد
    و پوشاک ، فعالان حوزه طراحی لباس ، علاقه‌مندان
    به صنایع دستی ، فعالان حوزه کیف و کفش های
    چرم و همه هنرمندانی که قصد دارند با سرمایه کم، کسب و کاری پررونق را شروع کنند،
    میباشد لذا با شرکت در این دوره
    به خوبی با تمام مباحث چرم دوزی
    آشنا خواهند شد.

  40. Моему котенку потребовалась неотложная медицинская помощь, и я не мог себе позволить откладывать визит к ветеринару. Благодаря сервису, я смог оперативно взять займ и обеспечить своего пушистого спутника всем необходимым для выздоровления.

  41. عکاسی و فیلمبرداری است که از گرفتن عکس و فیلم از یک رویداد کوچک با
    استفاده از نور موجود تا تصویری تبلیغاتی با نورپردازی خاص، در هر نوع تصویربرداری بسیار مهم است.
    نور، ماهیت تصویر (عکاسی و فیلم) را تشکیل می‌دهد

  42. Plenty of pg slot promotions, easy to play, really pay, really win, must be pg slot only! Play slots at pg slot, a direct website that provides first-class online slot games. Try playing for free with bonuses.

  43. İroko deck, İroko deck fiyat, iroko deck m2 fiyat, Ahşap Deck m2 fiyatı, Kompozit Deck m2 fiyatı, Ahşap Deck Fiyatları, Kompozit Deck m2 fiyatı İzmir, Ahşap Deck, Ahşap deck m2 fiyat, Teak deck, Teak deck m2 fiyat, Thermowood deck fiyat

  44. İroko deck, İroko deck fiyat, iroko deck m2 fiyat, Ahşap Deck m2 fiyatı, Kompozit Deck m2 fiyatı, Ahşap Deck Fiyatları, Kompozit Deck m2 fiyatı İzmir, Ahşap Deck, Ahşap deck m2 fiyat, Teak deck, Teak deck m2 fiyat, Thermowood deck fiyat

  45. I strongly recommend to avoid this platform. My own encounter with it was nothing but disappointment and concerns regarding fraudulent activities. Proceed with extreme caution, or alternatively, look for a trustworthy platform to meet your needs.

  46. I highly advise to avoid this platform. The experience I had with it was purely disappointment along with concerns regarding fraudulent activities. Proceed with extreme caution, or even better, look for a more reputable site to meet your needs.

  47. I strongly recommend steer clear of this platform. The experience I had with it has been nothing but frustration along with suspicion of deceptive behavior. Be extremely cautious, or better yet, seek out a trustworthy site for your needs.

  48. I highly advise stay away from this platform. The experience I had with it has been purely dismay along with doubts about deceptive behavior. Exercise extreme caution, or better yet, look for a trustworthy service to fulfill your requirements.

Leave a Reply

Your email address will not be published. Required fields are marked *