Try to solve problems in JavaScript, Python, and Java.
This is TIL(memo of key learnings) for solving problems in these languages,
but mostly python.

---

Solved Problems 📝

241210

• 108. Convert Sorted Array to Binary Search Tree

---

Key Learnings 🤔

what is Height-Balanced BST?

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

Depth is defined as the number of edges from the node to the deepest leaf in its subtree.

why balance matters?

Operations like search, insertion, and deletion in a balanced binary search tree have a time complexity of O(log N) due to the reduced height.

examples:

Balanced tree.

   4 
  / \ 
  2 6 
/ \ / \ 
1 3 5 7

• Depth of left subtree (rooted at 2): 2
• Depth of right subtree (rooted at 6): 2
• Difference: ∣2−2∣=0 (Balanced)

Still balanced tree.

   4 
  / \ 
  2 6 
/ \ 
1 3 

• Depth of left subtree (rooted at 2): 2
• Depth of right subtree (rooted at 6): 1
• Difference: ∣2−1∣=1 (Balanced)

💡
Maintaining balance ensures that the binary tree is efficient and avoids excessive height growth.

How to Build a Balanced BST?

So, definition of a balanced binary search tree is "The depth of the left and right subtrees of every node differs by at most 1".

The key is that the tree remains balanced as long as the depth of the left and right subtrees are not differ by more than 1.

There are middle elements as a single center(odd-sized arrays) or two possible middle elements as there is no single center(even-sized arrays).

If there are two middle elements? you can choose either one of the middle elements as the root, and the tree will still be height-balanced. The choice affects the shape of the tree but not the balance.

1. Use the middle element(or one of the middle element) as the root.
2. Recursively apply the process for the left and right halves of the array.

How to Truncate Numbers to Fixed Decimal Places in Python?

like toFixed(0) in js.

1. int()
2. math.floor()
3. can use String Manipulation 🤔

nums = [0, 1, 2, 3, 4]
center = len(nums) / 2  # 2.5
fixedCenter = int(center) # 2
fixedCenter = math.floor(center) # 2
fixedCenter = int(str(center).split('.')[0]) # 2 🤔

Recursive Function for Balanced BST in python.

Use recursion to divide the array until it’s empty and assign middle elements to nodes.

# Create a TreeNode with the middle element
middle_node = TreeNode(nums[center])

# Recursively build left and right subtrees
middle_node.left = sortedArrayToBST(nums[:center])  # Left half
middle_node.right = sortedArrayToBST(nums[center + 1:])  # Right half

Difference Between if nums is None: and if not nums:

For solving index is out of range error:

• if nums is None: Checks if nums is explicitly set to None.
• if not nums: Checks for all falsy values (None, [], '', 0, False).

👉 use if not nums: for cases like empty arrays or strings.

How to Divide an Array Into Two Halves in Java?

For java, array has a fixed size, cannot directly implement a slicing operation like nums[:center]. Can't directly divide an array in place without creating new arrays.

Instead, use Arrays.copyOfRange().

Solution: https://github.com/dusunax/algorithm/blob/main/0108-convert-sorted-array-to-binary-search-tree/0108-convert-sorted-array-to-binary-search-tree.java

int mid = nums.length / 2;
TreeNode midNode = new TreeNode(nums[mid]);

int[] leftHalf = Arrays.copyOfRange(nums, 0, mid);
int[] rightHalf = Arrays.copyOfRange(nums, mid + 1, nums.length);

midNode.left = makeBalancedBST(leftHalf);
midNode.right = makeBalancedBST(rightHalf);

return midNode;