binary-search-tree

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1902 - Depth of BST Given Insertion Order

LeetCode Problem 1902 Difficulty: 🟡 Medium Topics: Array, Tree, Binary Search Tree, Binary Tree, Ordered Set Solution Problem Understanding The problem gives us an array order that represents the exact sequence in which values are inserted into a binary search tree, usually abbreviated as BST. The array is a permutation of integers from 1 to n , which means every value appears exactly once and there are no duplicates. We...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2476 - Closest Nodes Queries in a Binary Search Tree

LeetCode Problem 2476 Difficulty: 🟡 Medium Topics: Array, Binary Search, Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding The problem gives us the root of a binary search tree, abbreviated as BST, along with a list of query values. For every query, we must determine two numbers: The largest value in the BST that is less than or equal to the query. The smallest value in the...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1932 - Merge BSTs to Create Single BST

LeetCode Problem 1932 Difficulty: 🔴 Hard Topics: Array, Hash Table, Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding This problem asks us to take multiple very small binary search trees (BSTs), each with at most three nodes, and attempt to merge them into a single valid BST. Each tree is represented by its root node in the array trees . The only operation allowed is to attach...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 109 - Convert Sorted List to Binary Search Tree

LeetCode Problem 109 Difficulty: 🟡 Medium Topics: Linked List, Divide and Conquer, Tree, Binary Search Tree, Binary Tree Solution Problem Understanding The problem gives us the head of a singly linked list whose values are already sorted in ascending order. We must convert this linked list into a height balanced Binary Search Tree, usually abbreviated as BST. A Binary Search Tree has the property that: Every node in the left...

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST

LeetCode Problem 1569 Difficulty: 🔴 Hard Topics: Array, Math, Divide and Conquer, Dynamic Programming, Tree, Union-Find, Binary Search Tree, Memoization, Combinatorics, Binary Tree Solution Problem Understanding The problem gives us a permutation of integers from 1 to n , and we insert the numbers into an initially empty Binary Search Tree (BST) in the exact order they appear in the array. A BST has the following property: Values smaller than...

Practice › LeetCode › LeetCode 10xx ›

LeetCode 1038 - Binary Search Tree to Greater Sum Tree

LeetCode Problem 1038 Difficulty: 🟡 Medium Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding The problem gives us the root of a Binary Search Tree, abbreviated as BST, and asks us to transform it into a Greater Sum Tree. In a Binary Search Tree, every node follows an important ordering rule: All values in the left subtree are smaller than the current node. All values in...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 783 - Minimum Distance Between BST Nodes

LeetCode Problem 783 Difficulty: 🟢 Easy Topics: Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding The problem asks us to find the minimum difference between values of any two nodes in a Binary Search Tree (BST). In other words, given a BST, we need to calculate the smallest absolute difference |a - b| where a and b are values of two distinct nodes. The input...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 450 - Delete Node in a BST

LeetCode Problem 450 Difficulty: 🟡 Medium Topics: Tree, Binary Search Tree, Binary Tree Solution Problem Understanding The problem asks us to delete a node with a specific value, key , from a Binary Search Tree, abbreviated as BST, and return the possibly updated root of the tree. A Binary Search Tree has an important ordering property: Every node in the left subtree contains a value smaller than the current node....

Practice › LeetCode › LeetCode 03xx ›

LeetCode 333 - Largest BST Subtree

LeetCode Problem 333 Difficulty: 🟡 Medium Topics: Dynamic Programming, Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding The problem gives us the root of an arbitrary binary tree and asks us to find the size of the largest subtree that is also a valid Binary Search Tree, abbreviated as BST. A subtree is any node together with all of its descendants. This means we cannot selectively ignore...

Practice › LeetCode › LeetCode 00xx ›

LeetCode 96 - Unique Binary Search Trees

LeetCode Problem 96 Difficulty: 🟡 Medium Topics: Math, Dynamic Programming, Tree, Binary Search Tree, Binary Tree Solution LeetCode 96 - Unique Binary Search Trees Problem Understanding This problem asks us to determine how many structurally different Binary Search Trees, or BSTs, can be formed using the integers from 1 to n . A Binary Search Tree has an important property: Every value in the left subtree is smaller than the...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 426 - Convert Binary Search Tree to Sorted Doubly Linked List

LeetCode Problem 426 Difficulty: 🟡 Medium Topics: Linked List, Stack, Tree, Depth-First Search, Binary Search Tree, Binary Tree, Doubly-Linked List Solution Problem Understanding The problem asks us to transform a Binary Search Tree, abbreviated as BST, into a sorted circular doubly linked list. The transformation must happen in place, meaning we are not allowed to create entirely new nodes for the linked list. Instead, we reuse the existing tree nodes...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1373 - Maximum Sum BST in Binary Tree

LeetCode Problem 1373 Difficulty: 🔴 Hard Topics: Dynamic Programming, Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding This problem asks us to examine every possible subtree inside a binary tree and determine whether that subtree forms a valid Binary Search Tree, abbreviated as BST. Among all valid BST subtrees, we must return the maximum possible sum of node values. A subtree consists of a node together with...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 701 - Insert into a Binary Search Tree

LeetCode Problem 701 Difficulty: 🟡 Medium Topics: Tree, Binary Search Tree, Binary Tree Solution Problem Understanding This problem asks us to insert a new value into an existing Binary Search Tree, abbreviated as BST, while preserving the BST property. A Binary Search Tree is a binary tree with a special ordering rule: Every value in the left subtree of a node is smaller than the node’s value. Every value in...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 653 - Two Sum IV - Input is a BST

LeetCode Problem 653 Difficulty: 🟢 Easy Topics: Hash Table, Two Pointers, Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree Solution LeetCode 653, Two Sum IV - Input is a BST Problem Understanding This problem gives us the root of a Binary Search Tree (BST) and an integer k . We must determine whether there are two distinct nodes in the tree whose values add up to k ....

Practice › LeetCode › LeetCode 00xx ›

LeetCode 99 - Recover Binary Search Tree

LeetCode Problem 99 Difficulty: 🟡 Medium Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding The problem gives us the root of a binary search tree, but exactly two nodes in the tree have had their values swapped accidentally. Our task is to restore the tree so that it once again satisfies the binary search tree property, without modifying the tree structure itself. A binary search tree,...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 285 - Inorder Successor in BST

LeetCode Problem 285 Difficulty: 🟡 Medium Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding This problem asks us to find the in-order successor of a given node p inside a Binary Search Tree, abbreviated as BST. An in-order traversal of a BST visits nodes in sorted order: Traverse the left subtree Visit the current node Traverse the right subtree Because BSTs maintain the ordering property: Every...

Practice › LeetCode › LeetCode 12xx ›

LeetCode 1214 - Two Sum BSTs

LeetCode Problem 1214 Difficulty: 🟡 Medium Topics: Two Pointers, Binary Search, Stack, Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding The problem gives us two binary search trees, root1 and root2 , along with an integer target . We must determine whether there exists one node from the first tree and one node from the second tree such that their values add up exactly to target ....

Practice › LeetCode › LeetCode 00xx ›

LeetCode 98 - Validate Binary Search Tree

LeetCode Problem 98 Difficulty: 🟡 Medium Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding This problem asks us to determine whether a given binary tree satisfies the rules of a Binary Search Tree, commonly abbreviated as BST. A binary tree consists of nodes where each node contains a value and pointers to a left child and a right child. In a BST, every node must follow...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 270 - Closest Binary Search Tree Value

LeetCode Problem 270 Difficulty: 🟢 Easy Topics: Binary Search, Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding The problem gives us the root of a Binary Search Tree, abbreviated as BST, and a floating point target value. Our task is to return the integer value stored in the BST that is numerically closest to the target. A Binary Search Tree has a very important property: Every node...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 700 - Search in a Binary Search Tree

LeetCode Problem 700 Difficulty: 🟢 Easy Topics: Tree, Binary Search Tree, Binary Tree Solution Problem Understanding This problem gives us the root node of a Binary Search Tree, commonly abbreviated as a BST, along with an integer value val . Our goal is to locate the node whose value is exactly equal to val and return that node. Since the problem asks us to return the subtree rooted at that...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1382 - Balance a Binary Search Tree

LeetCode Problem 1382 Difficulty: 🟡 Medium Topics: Divide and Conquer, Greedy, Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Here is a complete, detailed technical solution guide for LeetCode 1382 - Balance a Binary Search Tree , following all your formatting rules. Problem Understanding The problem asks us to take a binary search tree (BST) that may be unbalanced and produce a new BST that is balanced while preserving...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 938 - Range Sum of BST

LeetCode Problem 938 Difficulty: 🟢 Easy Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding This problem gives us the root of a Binary Search Tree, abbreviated as BST, along with two integers, low and high . We must compute the sum of all node values whose values lie inside the inclusive range [low, high] . A Binary Search Tree has an important property: Every node in...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 669 - Trim a Binary Search Tree

LeetCode Problem 669 Difficulty: 🟡 Medium Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding LeetCode 669, Trim a Binary Search Tree, asks us to modify a binary search tree so that every remaining node has a value within the inclusive range [low, high] . The input consists of three parts: root , the root node of a valid binary search tree low , the minimum allowed...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 230 - Kth Smallest Element in a BST

LeetCode Problem 230 Difficulty: 🟡 Medium Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding This problem gives us the root of a Binary Search Tree, abbreviated as BST, along with an integer k . We need to return the kth smallest value in the tree. A Binary Search Tree has a very important property: Every value in the left subtree is smaller than the current node....

Practice › LeetCode › LeetCode 07xx ›

LeetCode 776 - Split BST

LeetCode Problem 776 Difficulty: 🟡 Medium Topics: Tree, Binary Search Tree, Recursion, Binary Tree Solution Problem Understanding The problem asks us to split a binary search tree (BST) into two separate subtrees based on a target value. Specifically, the first subtree should contain all nodes with values less than or equal to the target, and the second subtree should contain all nodes with values strictly greater than the target. Importantly,...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 235 - Lowest Common Ancestor of a Binary Search Tree

LeetCode Problem 235 Difficulty: 🟡 Medium Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding The problem asks us to find the Lowest Common Ancestor, commonly abbreviated as LCA, of two nodes in a Binary Search Tree (BST). A lowest common ancestor of two nodes p and q is the deepest node in the tree that has both p and q as descendants. A node is allowed...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 703 - Kth Largest Element in a Stream

LeetCode Problem 703 Difficulty: 🟢 Easy Topics: Tree, Design, Binary Search Tree, Heap (Priority Queue), Binary Tree, Data Stream Solution Problem Understanding The problem asks us to design a data structure that continuously tracks the kth largest element in a stream of integers. We are given an integer k and an initial list of numbers called nums . After initialization, new numbers are added one at a time using the...

Practice › LeetCode › LeetCode 00xx ›

LeetCode 95 - Unique Binary Search Trees II

LeetCode Problem 95 Difficulty: 🟡 Medium Topics: Dynamic Programming, Backtracking, Tree, Binary Search Tree, Binary Tree Solution Problem Understanding The problem asks us to generate all structurally unique binary search trees (BSTs) that contain exactly n nodes labeled from 1 to n . A BST is a binary tree where for every node, all values in the left subtree are smaller than the node, and all values in the right...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 501 - Find Mode in Binary Search Tree

LeetCode Problem 501 Difficulty: 🟢 Easy Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding This problem asks us to find the mode(s) in a Binary Search Tree (BST). A mode is the value that appears most frequently in the tree. Since duplicates are allowed in this BST definition, a value may occur multiple times. The input is the root node of a BST. Every node contains...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 255 - Verify Preorder Sequence in Binary Search Tree

LeetCode Problem 255 Difficulty: 🟡 Medium Topics: Array, Stack, Tree, Binary Search Tree, Recursion, Monotonic Stack, Binary Tree Solution Problem Understanding The problem gives an array of unique integers called preorder . This array is supposed to represent the preorder traversal of a binary search tree, and we must determine whether such a BST could actually exist. In a preorder traversal, nodes are visited in this order: Visit the current...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 173 - Binary Search Tree Iterator

LeetCode Problem 173 Difficulty: 🟡 Medium Topics: Stack, Tree, Design, Binary Search Tree, Binary Tree, Iterator Solution It looks like your prompt accidentally concatenated two problems. I will answer the second one, LeetCode 173 - Binary Search Tree Iterator , following your required format. Problem Understanding This problem asks us to design an iterator for a Binary Search Tree (BST) that returns values in in-order traversal order . In a...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 510 - Inorder Successor in BST II

LeetCode Problem 510 Difficulty: 🟡 Medium Topics: Tree, Binary Search Tree, Binary Tree Solution Problem Understanding This problem asks us to find the in-order successor of a given node inside a Binary Search Tree, abbreviated as BST. Unlike the classic version of the problem, we are not given access to the root of the tree. Instead, we are given only a pointer to a specific node, and each node contains...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 897 - Increasing Order Search Tree

LeetCode Problem 897 Difficulty: 🟢 Easy Topics: Stack, Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding This problem gives us the root of a Binary Search Tree, abbreviated as BST, and asks us to rearrange the tree into a very specific form. A Binary Search Tree has the property that for every node: All values in the left subtree are smaller All values in the right subtree...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 272 - Closest Binary Search Tree Value II

LeetCode Problem 272 Difficulty: 🔴 Hard Topics: Two Pointers, Stack, Tree, Depth-First Search, Binary Search Tree, Heap (Priority Queue), Binary Tree Solution Problem Understanding This problem asks us to find the k values in a Binary Search Tree, or BST, whose values are numerically closest to a given floating point target . A BST has a very important property: Every value in the left subtree is smaller than the current...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 538 - Convert BST to Greater Tree

LeetCode Problem 538 Difficulty: 🟡 Medium Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding This problem asks us to transform a Binary Search Tree, abbreviated as BST, into a "Greater Tree". In the transformed tree, every node's value should become: its original value plus the sum of all values greater than it in the original BST The structure of the tree does not change. Only the...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 108 - Convert Sorted Array to Binary Search Tree

LeetCode Problem 108 Difficulty: 🟢 Easy Topics: Array, Divide and Conquer, Tree, Binary Search Tree, Binary Tree Solution Problem Understanding The problem gives us a sorted integer array nums in strictly increasing order and asks us to convert it into a height-balanced binary search tree (BST) . A binary search tree is a binary tree where: Every node in the left subtree contains values smaller than the current node. Every...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 449 - Serialize and Deserialize BST

LeetCode Problem 449 Difficulty: 🟡 Medium Topics: String, Tree, Depth-First Search, Breadth-First Search, Design, Binary Search Tree, Binary Tree Solution Problem Understanding The problem asks us to design two operations for a Binary Search Tree, abbreviated as BST: serialize(root) converts the BST into a string representation. deserialize(data) reconstructs the exact same BST from that string. The important requirement is that the deserialized tree must match the original tree structure and...

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1586 - Binary Search Tree Iterator II

LeetCode Problem 1586 Difficulty: 🟡 Medium Topics: Stack, Tree, Design, Binary Search Tree, Binary Tree, Iterator Solution Problem Understanding The problem requires implementing a BSTIterator class that allows forward and backward traversal over the in-order sequence of a Binary Search Tree (BST). In-order traversal of a BST visits nodes in ascending order. The iterator must support four operations: next() , prev() , hasNext() , and hasPrev() . Initially, the iterator...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1305 - All Elements in Two Binary Search Trees

LeetCode Problem 1305 Difficulty: 🟡 Medium Topics: Tree, Depth-First Search, Binary Search Tree, Sorting, Binary Tree Solution Problem Understanding The problem gives us two binary search trees, root1 and root2 . A binary search tree, commonly abbreviated as BST, has the important property that for every node: All values in the left subtree are smaller than the node's value All values in the right subtree are larger than the node's...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 530 - Minimum Absolute Difference in BST

LeetCode Problem 530 Difficulty: 🟢 Easy Topics: Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree Solution Problem Understanding This problem gives us the root node of a Binary Search Tree, abbreviated as BST, and asks us to find the minimum absolute difference between the values of any two distinct nodes in the tree. A Binary Search Tree has a very important property: Every value in the left subtree...

Practice › LeetCode › LeetCode 10xx ›

LeetCode 1008 - Construct Binary Search Tree from Preorder Traversal

LeetCode Problem 1008 Difficulty: 🟡 Medium Topics: Array, Stack, Tree, Binary Search Tree, Monotonic Stack, Binary Tree Solution Let's dive deep and construct a thorough technical guide for LeetCode 1008, following your formatting rules. Problem Understanding The problem asks us to construct a binary search tree (BST) from a given preorder traversal array. A preorder traversal is defined as visiting the root node first, then recursively visiting the left subtree,...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1008: Construct Binary Search Tree from Preorder Traversal

Problem Restatement We are given the preorder traversal of a binary search tree (BST) in an array preorder . We need to reconstruct the BST and return its root. Recall that in a BST, for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. In preorder traversal, we visit the root before the left and right subtrees. The official constraints...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1038: Binary Search Tree to Greater Sum Tree

Problem Restatement We are given the root of a Binary Search Tree (BST). We need to convert it into a Greater Sum Tree (GST) where every node's value is replaced by the sum of all values greater than or equal to that node's original value in the tree. The official constraints state that the number of nodes is in [1, 100] and 0 <= Node.val <= 100 . Input and...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 897: Increasing Order Search Tree

Problem Restatement We are given the root of a binary search tree. We need to rearrange the tree in inorder order so that: Requirement Meaning New root The leftmost node of the original tree Left child Every node must have no left child Right child Each node may have one right child Order Nodes appear in increasing order The result should be a right-skewed tree, like a sorted linked list...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 938: Range Sum of BST

Problem Restatement We are given the root of a binary search tree and two integers: low high We need to return the sum of all node values that are inside the inclusive range: [low, high] Inclusive means both endpoints count. So a node value should be included if: low <= node.val <= high The official statement asks for the sum of values of all nodes in a BST whose values...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 700: Search in a Binary Search Tree

Problem Restatement We are given the root of a binary search tree and an integer val . We need to find the node whose value equals val . If the node exists, return that node. Returning the node means returning the entire subtree rooted at that node. If the node does not exist, return null . The official statement asks us to return the subtree rooted at the node whose...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 783: Minimum Distance Between BST Nodes

Problem Restatement We are given the root of a binary search tree. We need to return the minimum difference between the values of any two different nodes. Because the tree is a BST, an inorder traversal visits the node values in sorted order. So instead of comparing every pair of nodes, we only need to compare neighboring values in inorder order. Input and Output Item Meaning Input Root of a...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 669: Trim a Binary Search Tree

Problem Restatement We are given the root of a binary search tree and two boundaries: Variable Meaning low Lowest allowed node value high Highest allowed node value We need to trim the tree so that every remaining node value lies inside: [low, high] The relative structure of the remaining nodes must stay the same. If one remaining node was a descendant of another remaining node before trimming, it should still...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 510: Inorder Successor in BST II

Problem Restatement We are given a node in a binary search tree. Each node contains: Field Meaning val Node value left Left child right Right child parent Parent pointer We need to return the inorder successor of the given node. The inorder successor of a node is the next node visited during inorder traversal: left -> root -> right If no successor exists, return None . The official problem provides...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 653: Two Sum IV - Input is a BST

Problem Restatement We are given the root of a binary search tree and an integer k . We need to return True if there are two different nodes in the tree whose values add up to k . Otherwise, return False . The two values must come from two different nodes. We cannot use the same node twice. Input and Output Item Meaning Input The root of a binary search...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 538: Convert BST to Greater Tree

Problem Restatement We are given the root of a Binary Search Tree. We need to convert it into a greater tree. For every node, its new value should be: original node value + sum of all values greater than it The tree structure does not change. Only node values change. A BST has this ordering property: Location Value Rule Left subtree Smaller than the current node Current node Between left...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 776: Split BST

Problem Restatement We are given the root of a binary search tree and an integer target . We need to split the tree into two separate binary search trees: Tree Contains First tree All nodes with values <= target Second tree All nodes with values > target The tree may not contain a node whose value is exactly target . We should preserve the original parent-child relationships as much as...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 701: Insert into a Binary Search Tree

Problem Restatement We are given the root of a binary search tree and a value val . We need to insert val into the tree while keeping the binary search tree property valid. A binary search tree has this rule: Position Rule Left subtree Values are smaller than the current node Right subtree Values are greater than the current node The problem guarantees that val does not already exist in...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 501: Find Mode in Binary Search Tree

Problem Restatement We are given the root of a binary search tree that may contain duplicate values. We need to return all values that appear most frequently in the tree. A value with the highest frequency is called a mode. If more than one value has the same highest frequency, return all of them in any order. The official statement defines the input as a BST with duplicates and asks...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 530: Minimum Absolute Difference in BST

Problem Restatement We are given the root of a Binary Search Tree. We need to return the minimum absolute difference between the values of any two different nodes in the tree. The important property is that the tree is a BST. For every node: left subtree values < node value < right subtree values Because of this property, an inorder traversal visits the node values in sorted order. The problem...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 450: Delete Node in a BST

Problem Restatement We are given the root of a binary search tree and an integer key . We need to delete the node whose value equals key . After deletion, the tree must still be a valid binary search tree. Return the possibly updated root of the tree. The root can change. For example, if we delete the original root, some other node may become the new root. The official...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 449: Serialize and Deserialize BST

Problem Restatement We need to design two methods: Method Meaning serialize(root) Convert a BST into a string deserialize(data) Convert that string back into the original BST The tree is guaranteed to be a binary search tree. There is no required format. Any format is valid as long as deserializing the serialized string reconstructs the same BST. The encoded string should be as compact as possible. The number of nodes is...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 272: Closest Binary Search Tree Value II

Problem Restatement We are given: The root of a binary search tree A floating-point target An integer k We need to return the k values in the BST that are closest to target . The answer may be returned in any order. The problem guarantees that there is only one unique set of k closest values. Also, k is valid, so k does not exceed the number of nodes in...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 270: Closest Binary Search Tree Value

Problem Restatement We are given the root of a binary search tree and a target value. The target can be a floating-point number. We need to return the value in the BST that is closest to the target. If multiple values are equally close, return the smaller value. The tree contains between 1 and 10^4 nodes, node values are in [0, 10^9] , and the target is in [-10^9, 10^9]...

Practice › LeetCode › LeetCode (archived) › LeetCode 00xx ›

LeetCode 99: Recover Binary Search Tree

Problem Restatement We are given the root of a binary search tree. Exactly two node values were swapped by mistake. We need to recover the BST without changing its structure. That means we should only swap the two wrong values back. The official statement says exactly two nodes in a BST were swapped by mistake, and we must recover the tree without changing its structure. The number of nodes is...

Practice › LeetCode › LeetCode (archived) › LeetCode 00xx ›

LeetCode 98: Validate Binary Search Tree

Problem Restatement We are given the root of a binary tree. We need to return whether the tree is a valid binary search tree. A valid binary search tree has three rules: Rule Meaning Left subtree Every node must be strictly less than the current node Right subtree Every node must be strictly greater than the current node Recursive rule Both left and right subtrees must also be valid BSTs...

Practice › LeetCode › LeetCode (archived) › LeetCode 00xx ›

LeetCode 96: Unique Binary Search Trees

Problem Restatement We are given an integer n . We need to count how many structurally unique binary search trees can be built using exactly the values: 1, 2, 3, ..., n Each value must be used exactly once. The official problem asks for the number of structurally unique BSTs with exactly n nodes and unique values from 1 to n . The constraint is 1 <= n <= 19...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 173: Binary Search Tree Iterator

Problem Restatement We need to implement a class: BSTIterator It represents an iterator over the inorder traversal of a binary search tree. For a BST, inorder traversal visits values in ascending order. The class must support: Method Meaning BSTIterator(root) Initialize the iterator with the root of the BST next() Move to the next value and return it hasNext() Return whether there is still a next value The pointer starts before...

Practice › LeetCode › LeetCode (archived) › LeetCode 00xx ›

LeetCode 95: Unique Binary Search Trees II

Problem Restatement We are given an integer n . We need to generate all structurally unique binary search trees that contain exactly the values: 1, 2, 3, ..., n Each value must be used exactly once. The answer may be returned in any order. A binary search tree has this rule: Node relation Required value rule Left subtree Values smaller than the root Right subtree Values greater than the root...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 285: Inorder Successor in BST

Problem Restatement We are given the root of a binary search tree and a node p inside that tree. We need to return the inorder successor of p . In a binary search tree, inorder traversal visits nodes in sorted order. So the inorder successor of p is the node with the smallest value greater than p.val . If no such node exists, return None . The source statement defines...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 109: Convert Sorted List to Binary Search Tree

Problem Restatement We are given the head of a singly linked list whose values are sorted in ascending order. We need to convert this sorted linked list into a height-balanced binary search tree. The official problem defines a height-balanced binary tree as a binary tree where the depth difference between the two subtrees of every node never exceeds 1 . The resulting tree must satisfy the BST property: left subtree...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 108: Convert Sorted Array to Binary Search Tree

Problem Restatement We are given a sorted integer array nums in ascending order. We need to convert it into a height-balanced binary search tree. The official problem defines a height-balanced binary tree as a binary tree in which the depth difference between the two subtrees of every node is never more than 1 . The tree must also satisfy the binary search tree property: left subtree values < root value...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 235: Lowest Common Ancestor of a Binary Search Tree

Problem Restatement We are given: The root of a binary search tree Two nodes p and q We need to find their lowest common ancestor. The lowest common ancestor, usually called LCA, is the lowest node in the tree such that both p and q are descendants of that node. A node may be a descendant of itself. LeetCode examples include: Input: root = [6,2,8,0,4,7,9,null,null,3,5] p = 2 q =...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 230: Kth Smallest Element in a BST

Problem Restatement We are given the root of a binary search tree and an integer k . We need to return the k th smallest value among all node values in the tree. The counting is 1-indexed. So: k = 1 means the smallest value k = 2 means the second smallest value k = 3 means the third smallest value LeetCode states that 1 <= k <= n <=...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 333: Largest BST Subtree

Problem Restatement We are given the root of a binary tree. We need to find the size of the largest subtree that is also a valid Binary Search Tree (BST). The size of a subtree means the number of nodes inside it. A BST follows these rules: Rule Meaning Left subtree All values are smaller than the root Right subtree All values are larger than the root Recursive property Both...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 255: Verify Preorder Sequence in Binary Search Tree

Problem Restatement We are given an array of unique integers called preorder . We need to decide whether this array could be the preorder traversal of a binary search tree. In preorder traversal, nodes are visited in this order: Visit root. Visit left subtree. Visit right subtree. For a binary search tree: Position Rule Left subtree Values are smaller than the root Right subtree Values are larger than the root...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List

Problem Restatement We are given the root of a binary search tree. We need to convert the tree into a sorted circular doubly linked list in-place. “In-place” means we should reuse the existing tree nodes. We should not create new list nodes. After conversion: Tree Pointer List Meaning left previous node right next node The returned node should be the smallest node in the list. The list must also be...

Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Binary Tree Online Sort

Binary Tree Online Sort Binary tree online sort inserts elements into a binary search tree (BST) as they arrive, then produces sorted output via in-order traversal. You use it when data arrives incrementally and you want ordered queries or final sorted output without a separate sorting phase. Problem Given a stream ( x_1, x_2, \dots, x_n ), maintain a structure such that: insertion is performed online elements can be retrieved...

Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Tree Sort

Tree Sort Tree sort sorts a sequence by inserting its elements into a binary search tree, then reading the tree with an inorder traversal. The binary search tree property places smaller values in the left subtree and larger values in the right subtree, so inorder traversal visits values in sorted order. The algorithm is simple when a binary search tree is already available. Its performance depends heavily on tree balance....

#binary-search-tree

LeetCode 1902 - Depth of BST Given Insertion Order

LeetCode 2476 - Closest Nodes Queries in a Binary Search Tree

LeetCode 1932 - Merge BSTs to Create Single BST

LeetCode 109 - Convert Sorted List to Binary Search Tree

LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST

LeetCode 1038 - Binary Search Tree to Greater Sum Tree

LeetCode 783 - Minimum Distance Between BST Nodes

LeetCode 450 - Delete Node in a BST

LeetCode 333 - Largest BST Subtree

LeetCode 96 - Unique Binary Search Trees

LeetCode 426 - Convert Binary Search Tree to Sorted Doubly Linked List

LeetCode 1373 - Maximum Sum BST in Binary Tree

LeetCode 701 - Insert into a Binary Search Tree

LeetCode 653 - Two Sum IV - Input is a BST

LeetCode 99 - Recover Binary Search Tree

LeetCode 285 - Inorder Successor in BST

LeetCode 1214 - Two Sum BSTs

LeetCode 98 - Validate Binary Search Tree

LeetCode 270 - Closest Binary Search Tree Value

LeetCode 700 - Search in a Binary Search Tree

LeetCode 1382 - Balance a Binary Search Tree

LeetCode 938 - Range Sum of BST

LeetCode 669 - Trim a Binary Search Tree

LeetCode 230 - Kth Smallest Element in a BST

LeetCode 776 - Split BST

LeetCode 235 - Lowest Common Ancestor of a Binary Search Tree

LeetCode 703 - Kth Largest Element in a Stream

LeetCode 95 - Unique Binary Search Trees II

LeetCode 501 - Find Mode in Binary Search Tree

LeetCode 255 - Verify Preorder Sequence in Binary Search Tree

LeetCode 173 - Binary Search Tree Iterator

LeetCode 510 - Inorder Successor in BST II

LeetCode 897 - Increasing Order Search Tree

LeetCode 272 - Closest Binary Search Tree Value II

LeetCode 538 - Convert BST to Greater Tree

LeetCode 108 - Convert Sorted Array to Binary Search Tree

LeetCode 449 - Serialize and Deserialize BST

LeetCode 1586 - Binary Search Tree Iterator II

LeetCode 1305 - All Elements in Two Binary Search Trees

LeetCode 530 - Minimum Absolute Difference in BST

LeetCode 1008 - Construct Binary Search Tree from Preorder Traversal

LeetCode 1008: Construct Binary Search Tree from Preorder Traversal

LeetCode 1038: Binary Search Tree to Greater Sum Tree

LeetCode 897: Increasing Order Search Tree

LeetCode 938: Range Sum of BST

LeetCode 700: Search in a Binary Search Tree

LeetCode 783: Minimum Distance Between BST Nodes

LeetCode 669: Trim a Binary Search Tree

LeetCode 510: Inorder Successor in BST II

LeetCode 653: Two Sum IV - Input is a BST

LeetCode 538: Convert BST to Greater Tree

LeetCode 776: Split BST

LeetCode 701: Insert into a Binary Search Tree

LeetCode 501: Find Mode in Binary Search Tree

LeetCode 530: Minimum Absolute Difference in BST

LeetCode 450: Delete Node in a BST

LeetCode 449: Serialize and Deserialize BST

LeetCode 272: Closest Binary Search Tree Value II

LeetCode 270: Closest Binary Search Tree Value

LeetCode 99: Recover Binary Search Tree

LeetCode 98: Validate Binary Search Tree

LeetCode 96: Unique Binary Search Trees

LeetCode 173: Binary Search Tree Iterator

LeetCode 95: Unique Binary Search Trees II

LeetCode 285: Inorder Successor in BST

LeetCode 109: Convert Sorted List to Binary Search Tree

LeetCode 108: Convert Sorted Array to Binary Search Tree

LeetCode 235: Lowest Common Ancestor of a Binary Search Tree

LeetCode 230: Kth Smallest Element in a BST

LeetCode 333: Largest BST Subtree

LeetCode 255: Verify Preorder Sequence in Binary Search Tree

LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List

Binary Tree Online Sort

Tree Sort