# Posts tagged as “BST”

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Example 1:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.


Constraints:

• The number of nodes in the tree is between 1 and 10^4.
• The tree nodes will have distinct values between 1 and 10^5.

## Solution: Inorder + recursion

Use inorder traversal to collect a sorted array from BST. And then build a balanced BST from this sorted array in O(n) time.

Time complexity: O(n)
Space complexity: O(n)

## C++

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3   9
/   /
-10  5

## Solution: Recursion

Recursively build a BST for a given range.

def build(nums, l, r):
if l > r: return None
m = l + (r – l) / 2
root = TreeNode(nums[m])
root.left = build(nums, l, m – 1)
root.right = build(nums, m + 1, r)
return root

return build(nums, 0, len(nums) – 1)

Time complexity: O(n)
Space complexity: O(logn)

## JavaScript

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree:  root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.


Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.


Note:

• All of the nodes’ values will be unique.
• p and q are different and both values will exist in the BST.

## Solution: Recursion

Time complexity: O(n)
Space complexity: O(n)

## C++

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]


Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]


Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]


Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]


Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]


Constraints:

• Each tree has at most 5000 nodes.
• Each node’s value is between [-10^5, 10^5].

## Solution: Inorder traversal + Merge Sort

Time complexity: O(t1 + t2)
Space complexity: O(t1 + t2)

## C++/STL

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into sets of k consecutive numbers
Return True if its possibleotherwise return False.

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].


Example 2:

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].


Example 3:

Input: nums = [3,3,2,2,1,1], k = 3
Output: true


Example 4:

Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.


Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= nums.length

## Solution: BST + Greedy

Start from the smallest available number and find k consecutive numbers.

Time complexity: O(nlogn)
Space complexity: O(n)

## Solution 2: HashTable

Time complexity: O(n)
Space complexity: O(n)