Binary Search Trees: Case Studies and Applications
Explore case studies and main applications of Binary Search Trees (BST) through examples such as finding a value in a BST, determining the closest value to a target, finding the kth largest integer in a BST, and converting a sorted array into a height-balanced BST. Understand key concepts of BST operations and usage in various scenarios.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Topics covered Binary search trees Binary search tree case studies
Binary Search Tree (BST) Binary tree such that for each node v of the tree Elements in left subtree are Less than elements stored at v 58 Elements in right subtree are Greater than or equal to elements at v 31 90 In-order traversal of BST Gives the elements Sorted in ascending order 25 42 92 For instance, for tree above, in-order traversal yields 25, 31, 42, 58, 90, 92
BST: main application To find whether a given value y is in BST At each internal node If y < element at node Search continues in left subtree 58 31 90 If y >= element at node Search continues in right subtree 25 42 92 If y == element at node Search terminates successfully Example: LeetCode 700
BST: case study 1 Write a function that takes in a BST and a target int value And returns the closest value to that target You can assume that there will be one closest value Each BST node has an integer value, left and right children nodes BST property: Value at a given node is Strictly greater than values to its left And less than or equal to values to its right
BST: case study 2 Write a function that takes in a BST And returns the kth largest integer in the BST You can assume that There are only int values in the BST And that k is less than or equal to nb of nodes in BST Also, duplicate ints will be treated as distinct values In {5, 7, 7}, second largest value will be 7 not 5
BST: case study 3 (LeetCode 108) Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is a binary tree in which the heights of the left/right subtrees of every node never differ by more than one.
